算法步骤

Floyd算法参考CSDN文章

Dijkstra

Floyd

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
% 定义图的边和权重
s = [9 9 1 1 3 3 3 2 2 5 5 7 7 8]; % 起始节点编号
t = [1 2 2 3 4 6 7 4 5 4 7 6 8 6]; % 终止节点编号
w = [4 8 3 8 2 7 4 1 6 6 2 14 10 9]; % 边的权重

% 创建一个图形对象 G
G = graph(s,t,w);

% 绘制图形 G，并将边的权重添加到图形上
% G.Edges.Weight 表示图形对象 G 中所有边的权重值，'EdgeLabel' 表示在图形上显示这些权重值
plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2)
% 隐藏图形的坐标轴
set( gca, 'XTick', [], 'YTick', [] );

% shortestpath 函数计算从节点 9 到节点 8 的最短路径和路径长度，并将路径和路径长度分别存储在 P 和 d 中
[P,d] = shortestpath(G, 9, 8)
% 在图形 G 中高亮显示最短路径
% highlight 函数高亮图形对象 myplot 中的路径 P，'EdgeColor', 'r' 表示将路径颜色设置为红色。
myplot = plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2);
highlight(myplot, P, 'EdgeColor', 'r')


% 计算图形 G 中任意两点之间的最短路径矩阵
D = distances(G)
% 输出 1 到 2 的最短路径
D(1,2)
% 输出 9 到 4 的最短路径
D(9,4)
% 找出图形 G 中距离节点 2 不超过 10 的所有节点
[nodeIDs,dist] = nearest(G, 2, 10)

代码输出结果

1
2
3
P = 1×7
     9     1     2     4     3     7     8
d = 24

1
2
3
4
5
6
7
8
9
10
D = 9×9
     0     3     6     4     9    13    10    20     4
     3     0     3     1     6    10     7    17     7
     6     3     0     2     6     7     4    14    10
     4     1     2     0     6     9     6    16     8
     9     6     6     6     0    13     2    12    13
    13    10     7     9    13     0    11     9    17
    10     7     4     6     2    11     0    10    14
    20    17    14    16    12     9    10     0    24
     4     7    10     8    13    17    14    24     0
1
ans = 3
1
ans = 8
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
nodeIDs = 7×1
     4
     1
     3
     5
     7
     9
     6
dist = 7×1
     1
     3
     3
     6
     7
     7
    10