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
1701010100
1701010101
1701010102
1701010103
我和数学有约：趣味数学及算法解析 [:1701004267]
1701010104
我和数学有约：趣味数学及算法解析 第9章 程序之美
1701010105
1701010106
当涉及到具体的工程问题时，我们的理论推导很关键，但是理论推导过后，程序设计往往能够起到很重要的作用，好的程序设计能够很好地求解理论表达式，得到最优结果，也就是我们需要完好的组织程序结构——程序架构之美。
1701010107
1701010108
1701010109
1701010110
1701010111
我和数学有约：趣味数学及算法解析 [:1701004268]
1701010112
我和数学有约：趣味数学及算法解析 9.1 百花齐放之程序之美
1701010113
1701010114
程序的美要从两个方面进行品味，一是程序整体的架构之美；二是程序的代码实现之美。
1701010115
1701010116
（1）编码之美
1701010117
1701010118
编程就是利用计算机写出具体的实现流程代码，以解决问题的方法。
1701010119