%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
% Dijkstra Algorithm
% input:
% A :邻接矩阵,两个点间不可达则路径长度为0或Inf
% s :出发点
% d :终点
% output:
% e :最短路径长度
% L :最短路径
% usage
% [cost,rute] = dijkstra(Gragh, source, destination)
% example
% G = [0 3 9 0 0 0 0;
% 0 0 0 7 1 0 0;
% 0 2 0 7 0 0 0;
% 0 0 0 0 0 2 8;
% 0 0 4 5 0 9 0;
% 0 0 0 0 0 0 4;
% 0 0 0 0 0 0 0;
% ];
%[e L] = dijkstra(G , 1 ,7)
%~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
function [e,L] = dijkstra(A,s,d)
% 如果起点终点相同
if s==d
e=0;
L=[s];
else
% 将邻接矩阵的权值0初始化为inf
A=setupgraph(A,inf);
% 起点“归一化”将所有的起点转换为“1”,使算法具有普遍适应性
if d==1
d=s;
end
A=exchangenode(A,1,s);
% 矩阵W存储图中起点到其他各点的编号和距离(已选集合,并记录求解过程)
% 相当于s[]集合
% 第一行是编号,第二行是距离
lengthA=size(A,1);
W=zeros(lengthA);
for i=2:lengthA
W(1,i)=i;
W(2,i)=A(1,i);
end
% 矩阵D存储图中起点到所有各点的编号和距离(记录着每轮的最终结果)
% 相当于dist[]
% 第一列是距离,第二列是编号
D = zeros(lengthA,2);
for i=1:lengthA
D(i,1)=A(1,i);
D(i,2)=i;
end
% 矩阵D2存储图中起点到所有各点的编号和距离(未选集合)
D2=D(2:length(D),:);
L=2;
while L<=(size(W,1)-1)
L=L+1;
% 将未选集合中各点按起点到该点的距离排序,拿到距离最短的未选点编号
D2=sortrows(D2,1);
k=D2(1,2);
% 把距离起点最近的未选点加入已选集合,并把该点从未选集合中删去
W(L,1)=k;
D2(1,:)=[];
% 以该点作为桥梁更新起点到其他未选点的距离
for i=1:size(D2,1)
if D(D2(i,2),1)>(D(k,1)+A(k,D2(i,2)))
D(D2(i,2),1) = D(k,1)+A(k,D2(i,2));
D2(i,1) = D(D2(i,2),1);
end
end
% 记录当前循环下,起点到各点的距离
for i=2:length(A)
W(L,i)= D(i,1);
end
end
% 如果进行过起点“归一化”,则需要逆“归一化”
if d==s
L=[1];
else
L=[d];
end
%获取最短路径长度
e=W(size(W,1),d);
%通过遍历输出最短路径
%相当于path[]
L = listdijkstra(L,W,s,d);
if e==inf
e=0;
L=NaN;
disp('无最短路径解')
end
end