Dijkstra算法之matlab实现_netcostmatrix

首先感谢一位博主“乐观的阿锡”分享了K最短路径算法：
参考：
MATLAB-K最短路径算法(KSP,K-shortest pathes)

在学习上述K最短路径算法时，需要调用Dijkstra算法，
为方便大家调用，将之模块化，引用烦请标明出处。

function [pathout cost] = dijkstra(netCostMatrix, source, destination)

%Dijkstra算法以其提出者人名命名，理论部分请参考教材P269《最优化技术与数学建模》董文永等编清华大学出版社2010。
%代码已模块化，可以直接调用，引用请标注出处。
%若接收的destination不为空则返回起点到终点的路径和路径总权重，否则返回最短路径上前一节点的列坐标值和当前节点的永久标号值。

m=netCostMatrix;n=size(netCostMatrix,1);%CostMatrix为n*n矩阵，默认行为起点列为终点，没有通路时请赋值为inf。
lub(1:n)=0;lub(source)=1;%若求出最短路径的永久标号值，设路标为1，否则为0。
d(1:n)=inf;d(source)=0;%临时存放各点的标号值，当路标为1时临时标号值即为永久标号值。
pathnode(1:n)=0;%存放最短路径上当前节点的前一点的列坐标值。
count=1;
while count<n %应用Dijkstra算法n-1次可以求处所有点间的最短路径    
 yb=find(lub);%列出已在最短路径上的点，默认起点已标出
 wb=find(lub==0);%列出未在最短路径上的点
 tempvalue=inf;
 lastpoint=source;
 for i=1:length(yb)
     for j=1:length(wb)
         plus=d(yb(i))+m(yb(i),wb(j));%找到与已知最短路径相接的下一节点的临时标号值
         if plus<tempvalue %逐个比较，以找到与已知最短路径相接的最小标号值
             tempvalue=plus;
             lastpoint=wb(j);
             d(lastpoint)=tempvalue;             
             pathnode(lastpoint)=yb(i);
         end
     end
 end
 lub(lastpoint)=1;%使时临时标号值转为永久标号值
 count=count+1;
end

pathout=destination;%终点一定在最短路径上，通过回溯至起点找到最短路径
if ~isempty(destination)
    cost=d(destination);
    temptvalue=destination;
    for k=1:n
        pathout=[pathout,pathnode(temptvalue)];
        if source==pathnode(temptvalue) %判断是否到达起点，若是则回溯结束返回结果
            pathout=fliplr(pathout);
            return
        elseif~pathnode(temptvalue)%判断是否存在通路,若不存在则回溯结束返回结果
            pathout=[];
            cost=[];
            return
        else            
        temptvalue=pathnode(temptvalue);
        end
    end
else
    cost=d;
    pathout=pathnode;  
end
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53