学步园

对于权值非负的有向图单源最短路径求解，可以用Dijkstra算法。

伪代码：
Dijkstra(G, w, s)<br /> {<br /> for each vertex v in G<br /> {<br /> distance[v] = infinite<br /> parent[v] = NULL<br /> color[v] = WHITE<br /> }<br /> distance[s] = 0<br /> insert the vertexes into distance minimum heap Q<br /> while (!Q.empty())<br /> {<br /> u = ExtractMim(Q)<br /> color[u] = BLACK<br /> for each edge (u, v)<br /> {<br /> if (color[v] == WHITE)<br /> {<br /> if (distance[v] > distance[u] + w[u][v])<br /> {<br /> distance[v] = distance[u] + w[u][v]<br /> parent[v] = u<br /> }<br /> Decrease-Key(v)<br /> }<br /> }<br /> }<br /> }<br />
如果使普通最小堆，该算法的算法复杂度为O((E+V)logV)。
如果使用斐波那契堆，ExtractMin操作耗时O(logV)，DecreaseKey操作耗时O(1)，所以算法复杂度为O(VlogV + E)。