设计时间为O（k（| V | + | E |））的单源最短路径问题的算法 [英] Design an algorithm for the single source shortest path problem that runs in time O(k(|V|+|E|))
问题描述
假设我们得到的有向图 G =（V，E）具有可能的正和负边长，但没有负循环。设 s∈V 为给定的源
顶点。如果从s到s的最短路径，如何设计在时间 O（k（| V | + | E |））中运行的单源最短路径问题的算法其他任何顶点最多需要 k条边？
Suppose we are given a directed graph G = (V, E) with potentially positive and negative edge lengths, but no negative cycles. Let s ∈ V be a given source
vertex. How to design an algorithm for the single-source shortest path problem that runs in time O(k(|V | + |E|)) if the shortest paths from s to any other vertex takes at most k edges?
推荐答案
O（k（| V | + | E |））方法：
Here`s O(k(|V | + |E|)) approach:
- 我们可以使用经过一些修改的Bellman-Ford算法
- 创建数组D []以存储从节点s到某个节点u的最短路径
- 最初D [s] = 0，所有其他D [i] = + oo（无穷大）
- 现在，我们遍历所有边缘k次并放松它们之后，D [u]会在< = k边缘<之后保持从节点s到u的最短路径值。 / li>
-
因为任何su最短路径最多为k条边，所以我们可以在k条边上进行k次迭代后结束算法
- We can use Bellman-Ford algorithm with some modifications
- Create array D[] to store shortest path from node s to some node u
- initially D[s]=0, and all other D[i]=+oo (infinity)
- Now after we iterate throught all edges k times and relax them, D[u] holds shortest path value from node s to u after <=k edges
Because any s-u shortest path is atmost k edges, we can end algorithm after k iterations over edges
伪代码：
每个顶点v的顶点：
D [v]：= + oo
for each vertex v in vertices:
D[v] := +oo
D [s] = 0
D[s] = 0
重复k次：
每条边（u，v），权重为w：
，如果D [u] + w< D [v]：
D [v] = D [u] + w
repeat k times:
for each edge (u, v) with weight w in edges:
if D[u] + w < D[v]:
D[v] = D[u] + w
这篇关于设计时间为O（k（| V | + | E |））的单源最短路径问题的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
