algorithm - 试图理解 Dijkstra 的算法

Question

我正在努力更好地理解 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

Answer 1

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

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