重建DJIKSTRA算法的最短路径树的复杂性
这本书说：
在本节中，我们证明了植根于 源S可以在O（N + M）时间中重建，给定D [V]集合。 Dijkstra的算法使用S作为源产生的值。像我们 在表示DFS和BFS树时，我们将映射每个顶点v =/= s to partent u（可能是u = s），使得u是在v之前的顶点，从s到v。如果u是 在从s到v的最短路径上v之前的顶点，一定是 D [U] + W（U，V）= D [V]。相反，如果满足上述方程式， 然后，从s到u的最短路径，然后是边缘（u，v）是一个 v。我们实施的最短路径将基于 此逻辑，测试每个顶点V的所有传入边缘，寻找一个 （u，v）满足密钥方程式。运行时间为o（n + m）， 当我们考虑每个顶点和所有传入的边缘时。
这是实施的代码：
def shortest_path_tree(g, s, d):
"""Reconstruct shortest-path tree rooted at vertex s, given distance map d.
Return tree as a map from each reachable vertex v (other than s)
to the edge e=(u,v) that is used to reach v from its parent u in the tree.
"""
tree = {}
for v in d:
if v is not s:
for e in g.incident_edges(v, False): # consider INCOMING edges
u = e.opposite(v)
wgt = e.element()
if d[v] == d[u] + wgt:
tree[v] = e # edge e is used to reach v
return tree
谢谢！
I am currently reading Data Structures and Algorithms in Python and I am in Chapter 14 page 669. The book says that reconstructing a shortest path tree takes O(n+m) time. but given the code I couldn't understand why it's O(n+m) and not O(n*m) (because we have two nested for loops one over the vertices and the other over the incoming edges.)
The book says:
In this section, we demonstrate that the shortest-path tree rooted at
source s can be reconstructed in O(n + m) time, given the set of d[v]
values produced by Dijkstra’s algorithm using s as the source. As we
did when representing the DFS and BFS trees, we will map each vertex v
=/= s to a parent u (possibly, u = s), such that u is the vertex immediately before v on a shortest path from s to v. If u is the
vertex just before v on the shortest path from s to v, it must be that
d[u] + w(u, v) = d[v]. Conversely, if the above equation is satisfied,
then the shortest path from s to u, followed by the edge (u, v) is a
shortest path to v. Our implementation reconstructs the tree based on
this logic, testing all incoming edges to each vertex v, looking for a
(u, v) that satisfies the key equation. The running time is O(n + m),
as we consider each vertex and all incoming edges to those vertices.
and here is the code of the implementation:
def shortest_path_tree(g, s, d):
"""Reconstruct shortest-path tree rooted at vertex s, given distance map d.
Return tree as a map from each reachable vertex v (other than s)
to the edge e=(u,v) that is used to reach v from its parent u in the tree.
"""
tree = {}
for v in d:
if v is not s:
for e in g.incident_edges(v, False): # consider INCOMING edges
u = e.opposite(v)
wgt = e.element()
if d[v] == d[u] + wgt:
tree[v] = e # edge e is used to reach v
return tree
Thank you!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
让我们考虑您显示的代码的伪代码：
您可以看到每个边缘再访问一个节点。
想象一下m = 0，确切的访问数为节点的数量，
想象M = 1，确切的访问数为节点 +（通过边缘连接的两个节点每次多1个时间）
访问量=节点 +边数
因此，
o（n + m）的复杂性Lets consider pseudocode for the code you showed:
You can see that each edge adds one more visit to a node.
imagine m = 0, the exact number of visits is number of nodes
imagine m = 1, the exact number of visits is number of nodes + (1 more time each for the two nodes connected by the edge)
therefore number of visits = number of nodes + number of edges
and hence the complexity of
O(n + m)