我已经看过很多关于这个主题的帖子(即post1,post2,post3),但是这些帖子都没有提供备份相应查询的算法。因此,我不确定接受这些帖子的答案。 在这里,我提出了一个基于BFS的最短路径(单源)算法,适用于非负加权图。任何人都可以帮助我理解为什么BFS(根据以下基于BFS的算法)不用于此类问题(涉及加权图)!
算法:
SingleSourceShortestPath (G, w, s):
//G is graph, w is weight function, s is source vertex
//assume each vertex has 'col' (color), 'd' (distance), and 'p' (predecessor)
properties
Initialize all vertext's color to WHITE, distance to INFINITY (or a large number
larger than any edge's weight, and predecessor to NIL
Q:= initialize an empty queue
s.d=0
s.col=GREY //invariant, only GREY vertex goes inside the Q
Q.enqueue(s) //enqueue 's' to Q
while Q is not empty
u = Q.dequeue() //dequeue in FIFO manner
for each vertex v in adj[u] //adj[u] provides adjacency list of u
if v is WHITE or GREY //candidate for distance update
if u.d + w(u,v) < v.d //w(u,v) gives weight of the
//edge from u to v
v.d=u.d + w(u,v)
v.p=u
if v is WHITE
v.col=GREY //invariant, only GREY in Q
Q.enqueue(v)
end-if
end-if
end-if
end-for
u.col=BLACK //invariant, don't update any field of BLACK vertex.
// i.e. 'd' field is sealed
end-while
运行时:据我所知,它是包含初始化成本的O(| V | + | E |)
如果此算法类似于任何现有算法,请告诉我
由于伪代码是Dijksta的算法,其FIFO队列而不是优先级队列,总是根据距离进行排序。到目前为止,每个访问过的(黑色)顶点计算出的最短距离的关键不变量不一定正确。这就是为什么优先级队列是(正)加权图中距离计算必须的原因。
您可以将算法用于未加权的图形,或者通过用权重为n
替换每个边缘并使用由权重为1的边连接的n-1
顶点来使其未加权。
反例:
第一次Q.enqueue(s)
之后的计算状态:
第一次迭代后的计算状态:
重要的是,这个图是一个反例是adj[u] = adj[S] = [F, M]
而不是[M, F]
,因此F
首先由Q.enqueue(v)
排队
第二次迭代后的计算状态:
由于顶点F
首先由u = Q.dequeue()
出列(与使用距离优先级队列时不同),此迭代不会更新任何距离,F
将变为黑色并且将违反不变量。
最后一次迭代后的计算状态:
看起来你实现了Dijkstra的经典算法,没有堆。您将通过每个边缘的矩阵,然后查看是否可以改善距离。
我曾经有同样的困惑。查看SPFA算法。当作者在1994年发表这个算法时,他声称它具有比Dijkstra更好的性能,具有O(E)复杂性,这是错误的。
您可以将此算法视为Bellman-Ford的变体/改进。最坏情况复杂性仍然是O(VE),因为一个节点可以多次从队列中添加/删除。但是对于随机稀疏图,它绝对优于原始的Bellman-Ford,因为它跳过了许多不必要的放松步骤。
尽管这个名称“SPFA”在学术界似乎并未被广泛接受,但由于其简单易用,因此在ACM学生中非常受欢迎。表现明智的Dijkstra是首选。