https://www.cnblogs.com/luxiaoxun/archive/2012/08/04/2622998.html
迪杰斯特拉算法（Dijkstra’s algorithm）是由荷兰计算机科学家艾兹赫尔·迪杰斯特拉提出。迪杰斯特拉算法使用了广度优先搜索解决非负权有向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。
该算法的输入包含了一个有权重的有向图 G，以及G中的一个来源顶点 S。我们以 V 表示 G 中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。(u, v) 表示从顶点 u 到 v 有路径相连。我们以 E 表示G中所有边的集合，而边的权重则由权重函数 w: E → [0, ∞] 定义。因此，w(u, v) 就是从顶点 u 到顶点 v 的非负权重（weight）。边的权重可以想像成两个顶点之间的距离。任两点间路径的权重，就是该路径上所有边的权重总和。已知有 V 中有顶点 s 及 t，Dijkstra 算法可以找到 s 到 t的最低权重路径(例如，最短路径)。这个算法也可以在一个图中，找到从一个顶点 s 到任何其他顶点的最短路径。对于不含负权的有向图，Dijkstra 算法是目前已知的最快的单源最短路径算法。
算法步骤：
1. 初始时令 S={V0},T={其余顶点}，T中顶点对应的距离值
若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值
若不存在<V0,Vi>，d(V0,Vi)为∞
2. 从T中选取一个其距离值为最小的顶点W且不在S中，加入S
3. 对其余T中顶点的距离值进行修改：若加进W作中间顶点，从 V0 到 Vi 的距离值缩短，则修改此距离值
重复上述步骤2、3，直到S中包含所有顶点，即W=Vi 为止
算法实现：
/*迪杰斯特拉算法： 求一个顶点到其他各顶点的最短路径。 算法： (a) 初始化：用起点v到该顶点w的直接边(弧)初始化最短路径，否则设为∞； (b) 从未求得最短路径的终点中选择路径长度最小的终点u：即求得v到u的最短路径； (c) 修改最短路径：计算u的邻接点的最短路径，若(v,…,u)+(u,w)<(v,…,w)，则以(v,…,u,w)代替。 (d) 重复(b)-(c)，直到求得v到其余所有顶点的最短路径。 特点：总是按照从小到大的顺序求得最短路径。 */ //单源最短路径dijkstra算法：s点到其他各顶点的最短路径 void Graph::dijkstra( Vertex s ) { for each Vertex v { v.dist = INFINITY; v.known = false; } s.dist = 0; for( ; ; ) { Vertex v = smallest unknown distance vertex; if( v == NOT_A_VERTEX ) break; v.known = true; for each Vertex w adjacent to v if( !w.known ) if( v.dist + cvw < w.dist ) { // Update w w.dist = v.dist + cvw; w.path = v; } } }
5.权值为1的单源最短路径
//图边的权值为1，最短路径：s点到其他各顶点的最短路径 void Graph::unweighted( Vertex s ) { for each Vertex v { v.dist = INFINITY; v.known = false; } s.dist = 0; for( int currDist = 0; currDist < NUM_VERTICES; currDist++ ) for each Vertex v if( !v.known && v.dist == currDist ) { v.known = true; for each Vertex w adjacent to v if( w.dist == INFINITY ) { w.dist = currDist + 1; w.path = v; } } }
使用队列queue实现：
//图边的权值为1，最短路径：s点到其他各顶点的最短路径 void Graph::unweighted( Vertex s ) { Queue<Vertex> q; for each Vertex v v.dist = INFINITY; s.dist = 0; q.enqueue( s ); while( !q.isEmpty( ) ) { Vertex v = q.dequeue( ); for each Vertex w adjacent to v if( w.dist == INFINITY ) { w.dist = v.dist + 1; w.path = v; q.enqueue( w ); } } }
6.有负边值的加权最短路径
//有负边值的加权最短路径算法 void Graph::weightedNegative( Vertex s ) { Queue<Vertex> q; for each Vertex v v.dist = INFINITY; s.dist = 0; q.enqueue( s ); while( !q.isEmpty( ) ) { Vertex v = q.dequeue( ); for each Vertex w adjacent to v if( v.dist + cvw < w.dist ) { // Update w w.dist = v.dist + cvw; w.path = v; if( w is not already in q ) q.enqueue( w ); } } }
7.计算任意两点间的最短路径
/** * Compute all-shortest paths. * a contains the adjacency matrix with a[ i ][ i ] presumed to be zero. * d contains the values of the shortest path. * Vertices are numbered starting at 0; all arrays have equal dimension. * A negative cycle exists if d[ i ][ i ] is set to a negative value. * Actual path can be computed using path[ ][ ]. * NOT_A_VERTEX is -1 */ void allPairs( const matrix<int> & a, matrix<int> & d, matrix<int> & path ) { int n = a.numrows( ); // Initialize d and path for( int i = 0; i < n; i++ ) for( int j = 0; j < n; j++ ) { d[ i ][ j ] = a[ i ][ j ]; path[ i ][ j ] = NOT_A_VERTEX; } for( int k = 0; k < n; k++ ) // Consider each vertex as an intermediate for( int i = 0; i < n; i++ ) for( int j = 0; j < n; j++ ) if( d[ i ][ k ] + d[ k ][ j ] < d[ i ][ j ] ) { // Update shortest path d[ i ][ j ] = d[ i ][ k ] + d[ k ][ j ]; path[ i ][ j ] = k; } }
评论