Page 209 - 数学建模算法与应用

第八章 图与网络模型及方法应用

d(i) 存放由始点到第 i 点最短通路的值。
求第一个城市到其他城市的最短路径的 Matlab 程序如下：
clc，clear

a=zeros(6)；
a(1，2)=50；a(1，4)=40；a(1，5)=25；a(1，6)=10；
a(2，3)=15；a(2，4)=20；a(2，6)=25；
a(3，4)=10；a(3，5)=20；

a(4，5)=10；a(4，6)=25；
a(5，6)=55；
a=a+a’；

a(find(a==0))=inf；
pb(1：length(a))=0；pb(1)=1；index1=1；index2=ones(1，length(a))；
d(1：length(a))=inf；d(1)=0；temp=1；
while sum(pb)<length(a)
tb=find(pb==0)；

d(tb)=min(d(tb)，d(temp)+a(temp，tb))；
tmpb=find(d(tb)==min(d(tb)))；
temp=tb(tmpb(1))；

pb(temp)=1；
index1=[index1，temp]；
temp2=find(d(index1)==d(temp)-a(temp，index1))；
index2(temp)=index1(temp2(1))；
end

d， index1， index2
我们编写的从起点 sb 到终点 db 通用的 Dijkstra 标号算法程序如下：function
[mydistance，mypath]=mydijkstra(a，sb，db)；

% 输入：a—邻接矩阵 (aij) 是指 i 到 j 之间的距离，可以是有向的
% sb—起点的标号， db—终点的标号
% 输出：mydistance—最短路的距离， mypath—最短路的路径
n=size(a，1)； visited(1：n) = 0；

199