试图理解 Dijkstra 算法
K22
我试图更好地理解 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
奇迹308
您可以在有向和无向图中使用 Dijkstra 算法，因为当您有一条从邻接列表前往的边时，您只需将边添加到 PriorityQueue 中。例如，如果我的一个节点有一条从 A 到 B 的权重为 3 的边，那么如果它是从 BI 引导的，则将无法将该边添加回 A，而从 AI 可以将其添加到 B。
像其他答案一样，请确保不要将其与权重混淆。Dijkstra 的算法在正加权图上运行，否则优先级队列将毫无用处。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
编辑于
相关文章
Related 相关文章
- 1
Dijkstra最短路径算法
- 2
网络建模图的Dijkstra算法
- 3
计算Dijkstra算法的跳跃次数？
- 4
是Dijkstra的算法，动态编程
- 5
Dijkstra算法：错误的路径
- 6
Dijkstra负权数算法
- 7
Dijkstra算法-以顶点为坐标
- 8
Dijkstra算法在Java中的实现
- 9
Dijkstra算法-复杂度
- 10
Dijkstra的算法-JavaScript实现
- 11
Dijkstra算法的复杂度
- 12
从前辈打印Dijkstra算法
- 13
与Dijkstra算法最短路径
- 14
实施Dijkstra算法的问题
- 15
实施Dijkstra算法的问题
- 16
Dijkstra算法比DFS快吗？
- 17
Python Dijkstra算法内存错误？
- 18
Dijkstra最短路径算法
- 19
Dijkstra的算法概念
- 20
Xcode Dijkstra算法
- 21
优化Dijkstra算法
- 22
Dijkstra算法：错误的路径
- 23
使用Python的Dijkstra算法
- 24
Dijkstra的算法-无限循环
- 25
Dijkstra的算法仿真
- 26
Dijkstra的算法-JavaScript实现
- 27
Dijkstra算法= SSSP
- 28
圈中的 Dijkstra 算法
- 29
需要帮助理解 Dijkstra 算法
我来说两句