0

我试图更好地理解 Dijkstra 算法。我附上了我教科书中的算法图像。伪代码显示输入是一个无向图，但算法对于有向图有什么不同吗？我用有向图的输入查找了算法，但没有发现任何差异。

Algorithm ShortestPath(G, v)

Input: A simple undirected weighted graph G with nonnegative edge weights and a distinguished vertex v of G

Output: A label D[u], for each vertex u of G, such that D[u] is the length of a shortest path from v to u in G

Initialize D[v]<--0 and D[u]<--+infinity for each vertex u != v.

Let priority queue Q contain all the vertices of G using the D labels as keys.

while Q is not empty do

    {pull a new vertex u into the cloud}

u<-- Q.removeMin()

for each vertex z adjacent to u such that z is in Q do

    {preform the relaxation procedure on edge (u,z)}

    if D[u]+w((u,z))<D[z] then

         D[z]<-- D[u]+w((u,z))

         change to D[z] the of vertex z in Q

return the label D[u] of each vertex u

Dijkstra 算法

4

1 回答 1

1

您可以在有向图和无向图中使用 Dijkstra 算法，因为当您从邻接列表中有一条要前往的边时，您只需将边添加到 PriorityQueue 中。例如，如果我的一个节点具有从 A 到 B 的权重为 3 的边，那么如果它是从 BI 定向的，则无法将边添加回 A，而从 AI 可以将其添加到 B。

与其他答案一样，请确保不要将其与权重混淆。Dijkstra 的算法在正加权图上运行，否则优先级队列将毫无用处。

于 2017-08-04T19:44:08.780 回答