0001 template <typename Tv, typename Te> //最短路径Dijkstra算法：适用于一般的有向图
0002 void Graph<Tv, Te>::dijk(Rank s) { //s < n
0003    reset();  prio(s) = 0;
0004    for (Rank i = 0; i < n; i++) { //共需引入n个顶点和n-1条边
0005       status(s) = VISITED;
0006       if (s != 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) && (prio(j) > prio(s) + wt(s, j))) //对邻接顶点j做松弛
0009             { prio(j) = prio(s) + wt(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 > prio(j)))
0013             { shortest = prio(j);  s = j; }
0014    }
0015 } //对于无向连通图，假设每一条边表示为方向互逆、权重相等的一对边