dijkstra最短路算法

Halcom

dijkstra最短路算法

1. clc % 清屏
   
2. clear all;                                 % 删除workplace变量
   
3. close all;                                 % 关掉显示图形窗口
   
4. clc,clear,close all
   
5. W=[0 1 2 Inf 7 4 8 Inf ;     % 带权邻接矩阵
   
6.    1 0 2 5 Inf Inf 7 Inf ;
   
7.    2 2 0 1 5 Inf Inf Inf;
   
8.    Inf 5 1 0 3 Inf Inf 6 ;
   
9.    7 Inf 5 3 0 3 Inf 4 ;
   
10.    4 Inf Inf Inf 3 0 2 6;
    
11.    8 7 Inf Inf Inf 2 0 4;
    
12.    Inf Inf Inf 6 4 6 4 0];
    
13. [r_path, r_cost] = dijkstra(1, 8, W)  % 从1到8节点的最短路径

复制代码

dijkstra函数如下：

1. function [r_path, r_cost] = dijkstra(pathS, pathE, transmat)
   
2. % The Dijkstra's algorithm, Implemented by Yi Wang, 2005
   
3. %   pathS: 所求最短路径的起点
   
4. %   pathE :所求最短路径的终点
   
5. %   transmat: 图的转移矩阵或者邻接矩阵，应为方阵
   
6. if ( size(transmat,1) ~= size(transmat,2) )
   
7.   error( 'detect_cycles:Dijkstra_SC', ...
   
8.          'transmat has different width and heights' );
   
9. end
   
10. % 初始化:
    
11. %  noOfNode-图中的顶点数
    
12. %  parent(i)-节点i的父节点
    
13. %  distance(i)-从起点pathS的最短路径的长度
    
14. %  queue-图的广度遍历
    
15. noOfNode = size(transmat, 1);
    
16. for i = 1:noOfNode
    
17.   parent(i) = 0;       % 初值操作
    
18.   distance(i) = Inf;    % 初值操作
    
19. end
    
20. queue = [];           % 队列
    
21. 
    
22. % 由路径开始最短路计算
    
23. for i=1:noOfNode
    
24.   if transmat(pathS, i)~=Inf
    
25.     distance(i) = transmat(pathS, i);
    
26.     parent(i)   = pathS;  % 当前路径
    
27.     queue     = [queue i];
    
28.   end
    
29. end
    
30. 
    
31. % 对图进行广度遍历
    
32. while length(queue) ~= 0
    
33.   hopS  = queue(1);
    
34.   queue = queue(2:end);
    
35.   
    
36.   for hopE = 1:noOfNode
    
37.     if distance(hopE) > distance(hopS) + transmat(hopS,hopE)   % 如果当前距离大于转换后的距离
    
38.       distance(hopE) = distance(hopS) + transmat(hopS,hopE);  % 更新
    
39.       parent(hopE)   = hopS;
    
40.       queue         = [queue hopE];
    
41.     end
    
42.   end
    
43.   
    
44. end
    
45. 
    
46. % 回溯进行最短路径的查找
    
47. r_path = [pathE];   
    
48. i = parent(pathE);
    
49. 
    
50. while i~=pathS && i~=0
    
51.   r_path = [i r_path];
    
52.   i      = parent(i);
    
53. end
    
54. if i==pathS
    
55.   r_path = [i r_path];   % 记录
    
56. else
    
57.   r_path = []          % 清空
    
58. end
    
59. % 返回最短路径的权和
    
60. r_cost = distance(pathE);

复制代码

输出：

1. [r_path, r_cost] = dijkstra(1, 8, W)  % 从1到8节点的最短路径
   
2. r_path =
   
3. 
   
4.      1     3     4     8
   
5. 
   
6. 
   
7. r_cost =
   
8. 
   
9.      9

复制代码

1. [r_path, r_cost] = dijkstra(2, 8, W)  % 从1到8节点的最短路径
   
2. r_path =
   
3. 
   
4.      2     3     4     8
   
5. 
   
6. 
   
7. r_cost =
   
8. 
   
9.      9

复制代码

1. [r_path, r_cost] = dijkstra(3, 7, W)  % 从1到8节点的最短路径
   
2. 
   
3. r_path =
   
4. 
   
5.      3     1     6     7
   
6. 
   
7. 
   
8. r_cost =
   
9. 
   
10.      8

复制代码