1701010027
1701010028
1701010029
1701010030
图8-22 城市网络图
1701010031
1701010032
【分析】
1701010033
1701010034
根据图8-22写出图G的带权邻接矩阵：
1701010035
1701010036
1701010037
1701010038
1701010039
则相应的权值wij即是W的第i行第j列的元素。由于G是无向图，可见W为对称阵。
1701010040
1701010041
1701010042
（1）令，则有：
1701010043
1701010044
1701010045
1701010046
1701010047
1701010048
（2），则有：
1701010049
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