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
[
上一页 ]
[ :1.70101005e+09 ]
[
下一页 ]