0001 template <typename Tv, typename Te> //最短路径Dijkstra算法:适用于一般的有向图 0002 void Graph<Tv, Te>::dijkstra ( int s ) { //assert: 0 <= s < n 0003 reset(); priority ( s ) = 0; 0004 for ( int i = 0; i < n; i++ ) { //共需引入n个顶点和n-1条边 0005 status ( s ) = VISITED; 0006 if ( -1 != parent ( s ) ) type ( parent ( s ), s ) = TREE; //引入当前的s 0007 for ( int j = firstNbr ( s ); -1 < j; j = nextNbr ( s, j ) ) //枚举s的所有邻居j 0008 if ( ( status ( j ) == UNDISCOVERED ) && ( priority ( j ) > priority ( s ) + weight ( s, j ) ) ) //对邻接顶点j做松弛 0009 { priority ( j ) = priority ( s ) + weight ( s, j ); parent ( j ) = s; } //与Prim算法唯一的不同之处 0010 for ( int shortest = INT_MAX, j = 0; j < n; j++ ) //选出下一最近顶点 0011 if ( ( status ( j ) == UNDISCOVERED ) && ( shortest > priority ( j ) ) ) 0012 { shortest = priority ( j ); s = j; } 0013 } 0014 } //对于无向连通图,假设每一条边表示为方向互逆、权重相等的一对边