7.5.1 单源点路径问题 　　例如对有向网 G8 执行迪杰斯特拉算法的过程如动画所示。 算法 7.10 　　void ShortestPath_DIJ( MGraph G, VertexType u ) 　{ 　　// 用 Dijkstra 算法求有向网G从源点 u 到其余顶点的最短路径 　　s = LocateVex(G, u); 　　　　　// 源点 u 是图中第 s 个顶点 　　for ( i=0; i<G.vexnum; ++i) {
	final[i] = FALSE; dist[i] = G.arcs[s][i]; 　　　v=G.vexs[i]; 　　　if (dist[i] < INFINITY) path = uv ; 　　　　　　　　　　　　　　　　　// 已经找到一条从顶点 u 到顶点 v 的路径 　　　else path[i] = ; 　　　　　// 暂时没有路径 　　} // for 　　dist[s] = 0; final[s] = TRUE; // 初始化，顶点 u 属于S集 　　for (i=1; i<G.vexnum; ++i) 　　{ 　　　　　　　　　　　　　// 求从源点到其余顶点的最短路径顶点 　　　j = minimum(dist); 　　　　　　　// 在集合V-S的顶点中求当前已得到的最短路径长度最小值 　　　if (dist[j] == INFINITY) break; 　　　　　　　// V-S中剩余顶点不存在从顶点 u 到它们的路径 　　　final[j] = TRUE; 　　　　　// 当前离顶点 u 最近的 v 加入S集 　　　for (k=0; k<G.vexnum; ++k)　// 更新其它顶点的当前最短路径 　　　　if (!final[k] && (dist[j]+G.arcs[j][k]<dist[k])) { 　　　　　　　　　　　　　　　　　// 修改dist[k]和path[k] G.vexs[k]∈V-S		设 v=G.vexs[i]; 则final[i] 为TRUE表示 v∈S,即已经求得从 u 到 v 的最短路径。
	dist[k] = dist[j] + G.arcs[j][k]; 　　　　　path[k] = path[j]+ G.vexs[k] ; // "+"表示串的联接 　　　　} // if 　　　} // for k 　　} // for i 　} // ShortestPath_DIJ		容易分析出，迪杰斯特拉算法的时间复杂度和普里姆算法相同，也是O(n2)，即使是只要求求一条从源点到某个特定终点之间的最短路径，但如果是应用迪杰斯特拉算法的话，那么必须先求出所有"路径长度"比它短的最短路径，因此除非它是一条路径长度最短的最短路径，否则时间复杂度仍是O(n2)的。