最短路径的 Dijkstra 算法 The Dijkstra Algorithm eryar@163.com 摘要 : 本文用 C 实现了图的最短路径 Dijkstra 算法, 并将自己理解该算法的方式与大家 分享下, 若有错误之处, 欢迎指正 关键字 : 图 最短路径 Graph Dijkstra 一 引言 Introduction 对图 G 中的每一条边 e 都赋以一个实数 w(e), 则 G 连同它边上的权称为赋权图 赋权图经常出现在图论的实际应用问题中, 边上的权 (Weight) 可以表示各种实际意义, 如在输送网络中, 权可以表示两地的距离, 可以表示运输的时间, 还可以表示运输的费用等 许多最优化问题相当于在一个赋权图中找出某类具有最小 ( 或最大 ) 权的子图 例如, 给出一个连接各城镇的铁路网, 要找出一条给定两个城镇间的最短路线 这个问题的图论模型建立如下 : 以顶点代表城镇, 边代表城镇间的铁路线, 权表示直接相连的城镇之间的铁路距离, 得到一个赋权图, 即网络 N 本文讨论带权的有向图, 并称路径上的第一个顶点为源点 (Source), 最后一个顶点为终点 (Destination) 二 算法理解 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<, 所以将 v0 到 v3 的距离更新为 60, 如下表所示 : 源点终点 v1 v2 v3 v4 v5 v0 10 60 30 100 由上表可知, 与源点 v0 次近的顶点为 v4, 距离为 30 将 v4 加入到最终顶点集合 S 中 ; 再根据 v4 更新从源点到其它顶点的最短距离 即从 v0-v4-v3 的距离为 50<60, 所以将 v0 到 v3 的距离更新为 50; 从 v0-v4-v5 的距离为 90<100, 所以将 v0 到 v5 的距离更新为 90 源点终点 v1 v2 v3 v4 v5 v0 10 50 30 90 重复以上操作 直到最终集合包含了所有的顶点 三 程序实现 Code /* * Copyright (c) 2013 eryar All Rights Reserved. * * File : Main.cpp * Author : eryar@163.com * Date : 2013-1-1 16:50
* Version : 0.1v * * Description : Use adjacency matrix of a graph. * Use Dijkstra method to find the shortest path. * #include <CFLOAT> #include <IOSTREAM> using namespace std; const int VERTEX_NUM = 20; const double INFINITY = DBL_MAX; // Arc of the graph. typedef struct SArc double dweight; AdjMatrix[VERTEX_NUM][VERTEX_NUM]; // The graph: include vertex size and // arc size also the adjacency matrix. typedef struct SGraph int mvertexsize; int marcsize; int mvertex[vertex_num]; AdjMatrix madjmatrix; Graph; // Function declarations. void CreateGraph(Graph& graph, bool isdigraph = false); int LocateVertex(const Graph& graph, int vertex); void ShowGraph(const Graph& graph); void Dijkstra(const Graph& graph, int src); // Main function. int main(int argc, char* argv[]) Graph graph; int isrc = 0; CreateGraph(graph, true);
ShowGraph(graph); cout<<"input the source node of the shortest path:"; cin>>isrc; Dijkstra(graph, isrc); return 0; /** * brief Create the graph. * param [in/out] graph: the graph. * [in] isdigraph: Create a digraph when this flag set true. * return none. void CreateGraph( Graph& graph, bool isdigraph /*= false ) cout<<"create the graph"<<endl; cout<<"input vertex size:"; cin>>graph.mvertexsize; cout<<"input arc size:"; cin>>graph.marcsize; // Input vertex for (int ivertex = 0; ivertex < graph.mvertexsize; ivertex++) cout<<"input "<<ivertex+1<<" vertex value:"; cin>>graph.mvertex[ivertex]; // Initialize adjacency matrix. for (int i = 0; i < graph.mvertexsize; i++) for (int j = 0; j < graph.mvertexsize; j++) graph.madjmatrix[i][j].dweight = INFINITY; // Build adjacency matrix.
int iinitial = 0; int iterminal = 0; int xpos = 0; int ypos = 0; double dweight = 0; for (int k = 0; k < graph.marcsize; k++) cout<<"input "<<k+1<<" arc initial node:"; cin>>iinitial; cout<<"input "<<k+1<<" arc terminal node:"; cin>>iterminal; cout<<"input the weight:"; cin>>dweight; xpos = LocateVertex(graph, iinitial); ypos = LocateVertex(graph, iterminal); graph.madjmatrix[xpos][ypos].dweight = dweight; if (!isdigraph) graph.madjmatrix[ypos][xpos].dweight = dweight; /** * brief Show the weight of the graph arc. * param [in] graph * return none. void ShowGraph(const Graph& graph) cout<<"show the graph represented by adjacency matrix:"<<endl; // Output adjacency matrix. for (int m = 0; m < graph.mvertexsize; m++) for (int n = 0; n < graph.mvertexsize; n++)
cout<<graph.madjmatrix[m][n].dweight<<"\t"; cout<<endl; /** * brief Locate vertex position in the adjacency matrix. * param [in] graph: * [in] vertex: * return The position of the vertex. If not found return -1. int LocateVertex( const Graph& graph, int vertex ) for (int i = 0; i < graph.mvertexsize; i++) if (graph.mvertex[i] == vertex) return i; return -1; /** * brief Dijkstra algorithm to find the shortest path. * param [in] graph. * [in] source node. * return none. void Dijkstra(const Graph& graph, int src ) int imin = 0; double dmin = 0; double dtempmin = 0; // The distance between source node to the vi node. double ddist[vertex_num] = 0; // The set of all the shortest path node. bool bfinalset[vertex_num] = false;
// Initialize status: if there is an arc between // source node and vi node, set the distance to // its weight value. for (int i = 0; i < graph.mvertexsize; i++) bfinalset[i] = false; ddist[i] = graph.madjmatrix[src][i].dweight; // Mark the visit flag. ddist[src] = 0; bfinalset[src] = true; // Dijstra algorithm: other N-1 vertex. for (int j = 1; j < graph.mvertexsize; j++) // Find a vertex that its distance is the shortest // to the source node. dmin = INFINITY; for (int k = 0; k < graph.mvertexsize; k++) if ((!bfinalset[k]) && (ddist[k] <= dmin)) imin = k; dmin = ddist[k]; // Add the nearest vertex to the final set. bfinalset[imin] = true; // Output the shortest path vertex and its distance. cout<<"the shortest path between "<<src<<" and "<<imin<<" is: "<<dmin<<endl; // Update the shortest path. for (int l = 0; l < graph.mvertexsize; l++) dtempmin = dmin + graph.madjmatrix[imin][l].dweight; if ((!bfinalset[l]) && (dtempmin < ddist[l]))
ddist[l] = dtempmin; 以图 1 为例, 程序运行结果如下所示 : Create the graph Input vertex size:6 Input arc size:8 Input 1 vertex value:0 Input 2 vertex value:1 Input 3 vertex value:2 Input 4 vertex value:3 Input 5 vertex value:4 Input 6 vertex value:5 Input 1 arc initial node:0 Input 1 arc terminal node:2 Input the weight:10 Input 2 arc initial node:0 Input 2 arc terminal node:4 Input the weight:30 Input 3 arc initial node:0 Input 3 arc terminal node:5 Input the weight:100 Input 4 arc initial node:1 Input 4 arc terminal node:2 Input the weight:5 Input 5 arc initial node:2 Input 5 arc terminal node:3 Input the weight:50 Input 6 arc initial node:3 Input 6 arc terminal node:5 Input the weight:10 Input 7 arc initial node:4 Input 7 arc terminal node:3 Input the weight:20 Input 8 arc initial node:4 Input 8 arc terminal node:5 Input the weight:60 Show the graph represented by adjacency matrix: 1.79769e+308 1.79769e+308 10 1.79769e+308 30 100 1.79769e+308 1.79769e+308 5 1.79769e+308 1.79769e+308 1.79769e
+308 1.79769e+308 1.79769e+308 1.79769e+308 50 1.79769e+308 1.79769e +308 1.79769e+308 1.79769e+308 1.79769e+308 1.79769e+308 1.79769e+308 10 1.79769e+308 1.79769e+308 1.79769e+308 20 1.79769e+308 60 1.79769e+308 1.79769e+308 1.79769e+308 1.79769e+308 1.79769e+308 1.79769e+308 Input the source node of the shortest path:0 The shortest path between 0 and 2 is: 10 The shortest path between 0 and 4 is: 30 The shortest path between 0 and 3 is: 50 The shortest path between 0 and 5 is: 60 The shortest path between 0 and 1 is: 1.79769e+308 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 语言版 ) 清华大学出版社