0001 template <typename Tv, typename Te> //最短路径Dijkstra算法：适用于一般的有向图
0002 void Graph<Tv, Te>::dijkstra( Rank s ) { // s < n
0003    reset(); priority( s ) = 0;
0004    for ( Rank 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 ( Rank 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       int shortest = INT_MAX;
0011       for ( Rank j = 0; j < n; j++ ) //选出下一最近顶点
0012          if ( ( status( j ) == UNDISCOVERED ) && ( shortest > priority( j ) ) )
0013             { shortest = priority( j ); s = j; }
0014    }
0015 } //对于无向连通图，假设每一条边表示为方向互逆、权重相等的一对边