posts - 336, comments - 537, trackbacks - 0, articles - 0

The Dijkstra Algorithm

Posted on 2013-01-01 22:38 eryar 阅读(7973) 评论(0)  编辑 收藏 引用

最短路径的Dijkstra算法

The Dijkstra Algorithm

eryar@163.com

摘要:本文用C实现了图的最短路径Dijkstra算法,并将自己理解该算法的方式与大家分享下,若有错误之处,欢迎指正。

关键字:图、最短路径、GraphDijkstra

一、引言 Introduction

对图G中的每一条边e都赋以一个实数w(e),则G连同它边上的权称为赋权图。赋权图经常出现在图论的实际应用问题中,边上的权(Weight)可以表示各种实际意义,如在输送网络中,权可以表示两地的距离,可以表示运输的时间,还可以表示运输的费用等。许多最优化问题相当于在一个赋权图中找出某类具有最小(或最大)权的子图。例如,给出一个连接各城镇的铁路网,要找出一条给定两个城镇间的最短路线。这个问题的图论模型建立如下:以顶点代表城镇,边代表城镇间的铁路线,权表示直接相连的城镇之间的铁路距离,得到一个赋权图,即网络N

本文讨论带权的有向图,并称路径上的第一个顶点为源点(Source),最后一个顶点为终点(Destination)。

Dijkstra_Animation

二、算法理解 Understanding the Algorithm

Dijkstra算法描述为:假设用带权邻接矩阵来表示带权有向图。首先引进一个辅助向量D,它的每个分量D[i]表示当前所找到的从始点v到每个终点Vi的最短路径。它的初始状态为:若两顶点之间有弧,则D[i]为弧上的权值;否则置D[i]为无穷大。

u 找到与源点v最近的顶点,并将该顶点并入最终集合S

u 根据找到的最近的顶点更新从源点v出发到集合V-S上可达顶点的最短路径;

u 重复以上操作。

1 带权有向图

以前总是认为Dijkstra算法可以用来求从源点到指定终点的最短路径,导致总不能抓住算法的中心思想。现在认为把握Dijkstra的算法要点为:

u Dijkstra提出了一个按路径长度递增的次序产生最短路径的算法;

u 每次循环都可以得到一个从源点到某个顶点的最短路径,某个即不是确定的一个;

以带权有向图1为例说明Dijkstra算法的执行过程:假设源点为v0,则初始状态时源点到其它各顶点的距离为:

源点 终点

v1

v2

v3

v4

v5

v0

10

30

100

由上表可知,与源点v0最近的顶点为v2,距离为10

v2加入到最终顶点集合S中。

再根据v2更新从源点到其它顶点的最短距离,即从v0-v2-v3的距离为60<∽,所以将v0v3的距离更新为60,如下表所示:

源点 终点

v1

v2

v3

v4

v5

v0

10

60

30

100

由上表可知,与源点v0次近的顶点为v4,距离为30

v4加入到最终顶点集合S中;

再根据v4更新从源点到其它顶点的最短距离。即从v0-v4-v3的距离为50<60,所以将v0v3的距离更新为50;从v0-v4-v5的距离为90<100,所以将v0v5的距离更新为90

源点 终点

v1

v2

v3

v4

v5

v0

10

50

30

90

重复以上操作……

直到最终集合包含了所有的顶点。

三、程序实现 Code

  1 /*
  2  *    Copyright (c) 2013 eryar All Rights Reserved.
  3  *
  4  *        File    : Main.cpp
  5  *        Author  : eryar@163.com
  6  *        Date    : 2013-1-1 16:50
  7  *        Version : 0.1v
  8  *
  9  *    Description : Use adjacency matrix of a graph.
 10  *                Use Dijkstra method to find the shortest path.
 11  *
 12 */
 13 
 14 #include <CFLOAT>
 15 #include <IOSTREAM>
 16 using namespace std;
 17 
 18 const int VERTEX_NUM = 20;
 19 const double INFINITY = DBL_MAX;
 20 
 21 // Arc of the graph.
 22 typedef struct SArc
 23 {
 24     double  dWeight;
 25 }AdjMatrix[VERTEX_NUM][VERTEX_NUM];
 26 
 27 // The graph: include vertex size and
 28 // arc size also the adjacency matrix.
 29 typedef struct SGraph
 30 {
 31     int         mVertexSize;
 32     int         mArcSize;
 33     int         mVertex[VERTEX_NUM];
 34     AdjMatrix   mAdjMatrix;
 35 }Graph;
 36 
 37 // Function declarations.
 38 void    CreateGraph(Graph& graph, bool isDigraph = false);
 39 int     LocateVertex(const Graph& graph, int vertex);
 40 void    ShowGraph(const Graph& graph);
 41 void    Dijkstra(const Graph& graph, int src);
 42 
 43 // Main function.
 44 int main(int argc, char* argv[])
 45 {
 46     Graph   graph;
 47     int iSrc = 0;
 48 
 49     CreateGraph(graph, true);
 50 
 51     ShowGraph(graph);
 52 
 53     cout<<"Input the source node of the shortest path:";
 54     cin>>iSrc;
 55 
 56     Dijkstra(graph, iSrc);
 57 
 58     return 0;
 59 }
 60 
 61 /**
 62 * brief  Create the graph.
 63 * param  [in/out] graph: the graph.
 64 *        [in] isDigraph: Create a digraph when this flag set true.
 65 * return none.
 66 */
 67 void CreateGraph( Graph& graph, bool isDigraph /*= false*/ )
 68 {
 69     cout<<"Create the graph"<<endl;
 70     cout<<"Input vertex size:"; 
 71     cin>>graph.mVertexSize;
 72 
 73     cout<<"Input arc size:";
 74     cin>>graph.mArcSize;
 75 
 76     // Input vertex
 77     for (int iVertex = 0; iVertex < graph.mVertexSize; iVertex++)
 78     {
 79         cout<<"Input "<<iVertex+1<<" vertex value:";
 80         cin>>graph.mVertex[iVertex];
 81     }
 82 
 83     // Initialize adjacency matrix.
 84     for (int i = 0; i < graph.mVertexSize; i++)
 85     {
 86         for (int j = 0; j < graph.mVertexSize; j++)
 87         {
 88             graph.mAdjMatrix[i][j].dWeight   = INFINITY;
 89         }
 90     }
 91 
 92     // Build adjacency matrix.
 93     int     iInitial  = 0;
 94     int     iTerminal = 0;
 95     int     xPos    = 0;
 96     int     yPos    = 0;
 97     double  dWeight = 0;
 98 
 99     for (int k = 0; k < graph.mArcSize; k++)
100     {
101         cout<<"Input "<<k+1<<" arc initial node:";
102         cin>>iInitial;
103 
104         cout<<"Input "<<k+1<<" arc terminal node:";
105         cin>>iTerminal;
106 
107         cout<<"Input the weight:";
108         cin>>dWeight;
109 
110         xPos  = LocateVertex(graph, iInitial);
111         yPos  = LocateVertex(graph, iTerminal);
112 
113         graph.mAdjMatrix[xPos][yPos].dWeight = dWeight;
114 
115         if (!isDigraph)
116         {
117             graph.mAdjMatrix[yPos][xPos].dWeight = dWeight;
118         }
119     }
120 }
121 
122 /**
123 * brief  Show the weight of the graph arc.
124 * param  [in] graph
125 * return none.
126 */
127 void    ShowGraph(const Graph& graph)
128 {
129     cout<<"Show the graph represented by adjacency matrix:"<<endl;
130 
131     // Output adjacency matrix.
132     for (int m = 0; m < graph.mVertexSize; m++)
133     {
134         for (int n = 0; n < graph.mVertexSize; n++)
135         {
136             cout<<graph.mAdjMatrix[m][n].dWeight<<"\t";
137         }
138 
139         cout<<endl;
140     }
141 }
142 
143 /**
144 * brief  Locate vertex position in the adjacency matrix.
145 * param  [in] graph:
146 *        [in] vertex: 
147 * return The position of the vertex. If not found return -1.
148 */
149 int LocateVertex( const Graph& graph, int vertex )
150 {
151     for (int i = 0; i < graph.mVertexSize; i++)
152     {
153         if (graph.mVertex[i] == vertex)
154         {
155             return i;
156         }
157     }
158 
159     return -1;
160 }
161 
162 /**
163 * brief  Dijkstra algorithm to find the shortest path.
164 * param  [in] graph.
165 *        [in] source node.
166 * return none.
167 */
168 void Dijkstra(const Graph& graph, int src )
169 {
170     int iMin = 0;
171     double dMin = 0;
172     double dTempMin = 0;
173 
174     // The distance between source node to the vi node.
175     double dDist[VERTEX_NUM] = {0};
176 
177     // The set of all the shortest path node.
178     bool bFinalSet[VERTEX_NUM] = {false};
179 
180     // Initialize status: if there is an arc between
181     // source node and vi node, set the distance to 
182     // its weight value.
183     for (int i = 0; i < graph.mVertexSize; i++)
184     {
185         bFinalSet[i] = false;
186 
187         dDist[i] = graph.mAdjMatrix[src][i].dWeight;
188     }
189 
190     // Mark the visit flag.
191     dDist[src] = 0;
192     bFinalSet[src] = true;
193 
194     // Dijstra algorithm: other N-1 vertex.
195     for (int j = 1; j < graph.mVertexSize; j++)
196     {
197         // Find a vertex that its distance is the shortest
198         // to the source node.
199         dMin = INFINITY;
200 
201         for (int k = 0; k < graph.mVertexSize; k++)
202         {
203             if ((!bFinalSet[k]) && (dDist[k] <= dMin))
204             {  
205                 iMin = k;
206                 dMin = dDist[k];
207             }
208         }
209 
210         // Add the nearest vertex to the final set.
211         bFinalSet[iMin] = true;
212 
213         // Output the shortest path vertex and its distance.
214         cout<<"The shortest path between "<<src<<" and "<<iMin<<" is: "<<dMin<<endl;
215 
216         // Update the shortest path.
217         for (int l = 0; l < graph.mVertexSize; l++)
218         {
219             dTempMin = dMin + graph.mAdjMatrix[iMin][l].dWeight;
220 
221             if ((!bFinalSet[l]) && (dTempMin < dDist[l]))
222             {
223                 dDist[l] = dTempMin;
224             }
225         }
226     }
227 }
228 
以图1为例,程序运行结果如下所示:

  1: Create the graph
  2: Input vertex size:6
  3: Input arc size:8
  4: Input 1 vertex value:0
  5: Input 2 vertex value:1
  6: Input 3 vertex value:2
  7: Input 4 vertex value:3
  8: Input 5 vertex value:4
  9: Input 6 vertex value:5
 10: Input 1 arc initial node:0
 11: Input 1 arc terminal node:2
 12: Input the weight:10
 13: Input 2 arc initial node:0
 14: Input 2 arc terminal node:4
 15: Input the weight:30
 16: Input 3 arc initial node:0
 17: Input 3 arc terminal node:5
 18: Input the weight:100
 19: Input 4 arc initial node:1
 20: Input 4 arc terminal node:2
 21: Input the weight:5
 22: Input 5 arc initial node:2
 23: Input 5 arc terminal node:3
 24: Input the weight:50
 25: Input 6 arc initial node:3
 26: Input 6 arc terminal node:5
 27: Input the weight:10
 28: Input 7 arc initial node:4
 29: Input 7 arc terminal node:3
 30: Input the weight:20
 31: Input 8 arc initial node:4
 32: Input 8 arc terminal node:5
 33: Input the weight:60
 34: Show the graph represented by adjacency matrix:
 35: 1.79769e+308    1.79769e+308    10      1.79769e+308    30      100
 36: 1.79769e+308    1.79769e+308    5       1.79769e+308    1.79769e+308    1.79769e+308
 37: 1.79769e+308    1.79769e+308    1.79769e+308    50      1.79769e+308    1.79769e+308
 38: 1.79769e+308    1.79769e+308    1.79769e+308    1.79769e+308    1.79769e+308  10
 39: 1.79769e+308    1.79769e+308    1.79769e+308    20      1.79769e+308    60
 40: 1.79769e+308    1.79769e+308    1.79769e+308    1.79769e+308    1.79769e+308 1.79769e+308
 41: Input the source node of the shortest path:0
 42: The shortest path between 0 and 2 is: 10
 43: The shortest path between 0 and 4 is: 30
 44: The shortest path between 0 and 3 is: 50
 45: The shortest path between 0 and 5 is: 60
 46: The shortest path between 0 and 1 is: 1.79769e+308
 47: Press any key to continue

四、结论 Conclusion

程序运行结果表明,从源点到其余各顶点的最短路径是依路径长度递增的序列。若要想求从源点到指定终点的最短路径,运行Dijkstra算法时到指定终点即可结束。

五、参考资料

1. Wiki地址:http://en.wikipedia.org/wiki/Dijkstra's_algorithm

2. 具体讲解请看视频:http://video.sina.com.cn/v/b/79074990-1298777923.html

3. 严蔚敏、吴伟民 数据结构(C语言版) 清华大学出版社

 


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理