Question

dijkstra的matlab程序看不懂，求解！

clear;
clc;
M=10000;%无穷远距离
a(1,:)=[0,50,M,40,25,10];
a(2,:)=[zeros(1,2),15,20,M,25];
a(3,:)=[zeros(1,3),10,20,M];
a(4,:)=[zeros(1,4),10,25];
a(5,:)=[zeros(1,5),55];
a(6,:)=zeros(1,6);
a=a+a';%a66邻接矩阵，无向图
pb(1:length(a))=0;pb(1)=1;%存放p,t标号信息
index1=1;%存放标号顶点顺序
index2=ones(1,length(a));%存放始点到第i点最短通路中第i顶点前一顶点的序号
d(1:length(a))=M;d(1)=0;%存放由始点到第i点最短通路的值
temp=1;%算c1到其它点的最短路
while sum(pb)<length(a)
tb=find(pb==0);%开始算第tb个顶点的最短路
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];
index=index1(find(d(index1)==d(temp)-a(temp,index1)));
if length(index)>=2
index=index(1);
end
index2(temp)=index;
end
d, index1, index2

加注释行的我都看懂了，能给后面那些行做一下注释么，感激不尽！

Answer 1

clear;
clc;
M=10000;%无穷远距离
a(1,:)=[0,50,M,40,25,10];
a(2,:)=[zeros(1,2),15,20,M,25];
a(3,:)=[zeros(1,3),10,20,M];
a(4,:)=[zeros(1,4),10,25];
a(5,:)=[zeros(1,5),55];
a(6,:)=zeros(1,6);
a=a+a';%a66邻接矩阵，无向图
pb(1:length(a))=0;pb(1)=1;%存放p,t标号信息
index1=1;%存放标号顶点顺序
index2=ones(1,length(a));%存放始点到第i点最短通路中第i顶点前一顶点的序号
d(1:length(a))=M;d(1)=0;%存放由始点到第i点最短通路的值
temp=1;%算c1到其它点的最短路
while sum(pb)<length(a)
tb=find(pb==0);%找到标号为0的所有点
d(tb)=min(d(tb),d(temp)+a(temp,tb));%计算标号为0的点的最短路,其余已算过,再算结果还是一样
tmpb=find(d(tb)==min(d(tb)));%tmpb存储标号为0的点中最短路最短的点的tb值，即在find过程中的第几个
temp=tb(tmpb(1));%这个第几个在d中的真正位置
pb(temp)=1;%把这个点标号为1
index1=[index1,temp];%存放标号顶点顺序
index=index1(find(d(index1)==d(temp)-a(temp,index1)));
if length(index)>=2%判断这个点前面是否有点
index=index(1);
end
index2(temp)=index;%记下这个点前面的点的标号
end
d, index1, index2

Answer 2

参考dijkstra的标准算法：

1 function Dijkstra(Graph, source):
2 for each vertex v in Graph: // Initializations
3 dist[v] := infinity // Unknown distance function from source to v
4 previous[v] := undefined // Previous node in optimal path from source
5 dist[source] := 0 // Distance from source to source
6 Q := the set of all nodes in Graph
// All nodes in the graph are unoptimized – thus are in Q
7 while Q is not empty: // The main loop
8 u := vertex in Q with smallest dist[]
9 if dist[u] = infinity:
10 break // all remaining vertices are inaccessible
11 remove u from Q
12 for each neighbor v of u: // where v has not yet been removed from Q.
13 alt := dist[u] + dist_between(u, v)
14 if alt < dist[v]: // Relax (u,v,a)
15 dist[v] := alt
16 previous[v] := u
17 return previous[]

或者看这里，比较各种Dijkstra最短路算法的matlab代码
http://www.rexcel.us/?p=581

Answer 3

clear;
clc;
M=10000;%无穷远距离
a(1,:)=[0,50,M,40,25,10];
a(2,:)=[zeros(1,2),15,20,M,25];
a(3,:)=[zeros(1,3),10,20,M];
a(4,:)=[zeros(1,4),10,25];
a(5,:)=[zeros(1,5),55];
a(6,:)=zeros(1,6);
a=a+a';%a66邻接矩阵，无向图
pb(1:length(a))=0;pb(1)=1;%存放p,t标号信息
index1=1;%存放标号顶点顺序
index2=ones(1,length(a));%存放始点到第i点最短通路中第i顶点前一顶点的序号
d(1:length(a))=M;d(1)=0;%存放由始点到第i点最短通路的值
temp=1;%算c1到其它点的最短路
while
sum(pb)<length(a)
tb=find(pb==0);%找到标号为0的所有点
d(tb)=min(d(tb),d(temp)+a(temp,tb));%计算标号为0的点的最短路,其余已算过,再算结果还是一样
tmpb=find(d(tb)==min(d(tb)));%tmpb存储标号为0的点中最短路最短的点的tb值，即在find过程中的第几个
temp=tb(tmpb(1));%这个第几个在d中的真正位置
pb(temp)=1;%把这个点标号为1
index1=[index1,temp];%存放标号顶点顺序
index=index1(find(d(index1)==d(temp)-a(temp,index1)));
if
length(index)>=2%判断这个点前面是否有点
index=index(1);
end
index2(temp)=index;%记下这个点前面的点的标号
end
d,
index1,
index2