1701010050
1701010051
1701010052
1701010053
1701010054
（3）修正，则有公式：
1701010055
1701010056
1701010057
1701010058
1701010059
继续转（2），即按照下面的循环计算。
1701010060
1701010061
1701010062
（4），则有：
1701010063
1701010064
1701010065
1701010066
1701010067
1701010068
（5）修正，则有公式：
1701010069
1701010070
1701010071
1701010072
1701010073
编写dijkstra（）函数如下：
1701010074
1701010075
function [r_path, r_cost] = dijkstra(pathS, pathE, transmat) % pathS: 所求最短路径的起点 % pathE: 所求最短路径的终点 % transmat: 图的转移矩阵或者邻接矩阵，应为方阵 if ( size(transmat,1) ~= size(transmat,2) ) error( ‘detect_cycles:Dijkstra_SC’, … ‘transmat has different width and heights’ ); end %初始化: % noOfNode-图中的顶点数 % parent(i)-节点i的父节点 % distance(i)-从起点pathS的最短路径的长度 % queue-图的广度遍历 noOfNode = size(transmat, 1); for i = 1:noOfNode parent(i) = 0; distance(i) = Inf; end queue = []; %从pathS: 所求最短路径的起点开始寻找最短路径 for i=1:noOfNode if transmat(pathS, i)~=Inf distance(i) = transmat(pathS, i); parent(i) = pathS; queue = [queue i]; end end %对图进行广度遍历 while length(queue) ~= 0 hopS = queue(1); queue = queue(2:end); for hopE = 1:noOfNode if distance(hopE) < distance(hopS) + transmat(hopS,hopE) distance(hopE) = distance(hopS) + transmat(hopS,hopE); parent(hopE) = hopS; queue = [queue hopE]; end end end %回溯进行最短路径的查找 r_path = [pathE]; i = parent(pathE); while i~=pathS && i~=0 r_path = [i r_path]; i = parent(i); end if i==pathS r_path = [i r_path]; else r_path = [] end %返回最短路径的权和 r_cost = distance(pathE);
1701010076
1701010077
主程序如下：
1701010078
1701010079
clc %清屏 clear all; %删除workplace变量 close all; %关掉显示图形窗口 warning off %消除警告 W=[0 1 2 Inf 7 4 8 Inf ; 1 0 2 5 Inf Inf 7 Inf ; 2 2 0 1 5 Inf Inf Inf; Inf 5 1 0 3 Inf Inf 6 ; 7 Inf 5 3 0 3 Inf 4 ; 4 Inf Inf Inf 3 0 2 6; 8 7 Inf Inf Inf 2 0 4; Inf Inf Inf 6 4 6 4 0]; [r_path, r_cost] = dijkstra(1, 8, W)
1701010080
1701010081
运行程序输出结果如下：
1701010082
1701010083
r_path = 1 3 4 8 r_cost = 9
1701010084
1701010085
整理结果如下：
1701010086
1701010087
1701010088
1701010089
1701010090
有结果可知从城市v1到城市v8的最短距离为9，中间需要经过城市v3和城市v4。具体如图8-23所示。
1701010091
1701010092
1701010093
1701010094
1701010095
1701010096
图8-23 最短路径图
1701010097
1701010098
最小树模型和最短路模型有区别，最短路问题强调用户从起点到终点的最短路程，即所耗费的资源最小，而最小树模型是链接所有节点，构成的网络的权值是最小的。最短路模型在现实中应用广泛，特别是对于物流运输业而言，当然是路程越短越好，节约时间和成本，一直是企业追求的目标，然而最短路模型能够为用户提供技术支持。
1701010099