从源到图中所有节点的最短路径距离 - O(m + n log(n)) 时间
Shortest path distance from source(s) to all nodes in the graph - O(m + n log(n)) time
令 G(V,E) 为具有边长的有向加权图，其中除两条边的边长为负外，所有边长均为正。给定一个固定的顶点 s，给出一个算法在 O(e + v log(v)) 时间内计算从 s 到任何其他顶点的最短路径。
我的作品：
我正在考虑使用 Johnson 算法的重新加权技术。然后，运行 Belford Algo 一次并应用 Dijkstra v 次。这将使我的时间复杂度为 O(v^2 log v + ve)。
这是标准的全对最短问题，因为我只需要一个顶点 - 我的时间复杂度将是 O(v log v + e) 对吗？
For this kind of problem, changing the graph is often a lot easier than changing the algorithm. Let's call the two negative-weight edges N1 and N2; a path by definition cannot use the same edge more than once, so there are four kinds of path:
- A. Those which use neither N1 nor N2,
- B. Those which use N1 but not N2,
- C. Those which use N2 but not N1,
- D. Those which use both N1 and N2.
So we can construct a new graph with four copies of each node from the original graph, such that for each node u in the original graph, (u, A), (u, B), (u, C) and (u, D) are nodes in the new graph. The edges in the new graph are as follows:
- For each positive weight edge
u-v in the original graph, there are four copies of this edge in the new graph, (u, A)-(v, A) ... (u, D)-(v, D). Each edge in the new graph has the same weight as the corresponding edge in the original graph.
- For the first negative-weight edge (N1), there are two copies of this edge in the new graph; one from layer A to layer B, and one from layer C to layer D. These new edges have weight 0.
- For the second negative-weight edge (N2), there are two copies of this edge in the new graph; one from layer A to layer C, and one from layer B to layer D. These new edges have weight 0.
Now we can 运行 any standard single-source shortest-path problem, e.g. Dijkstra's algorithm, just once on the new graph. The shortest path from the source to a node u in the original graph will be one of the following four paths in the new graph, whichever corresponds to a path of the lowest weight in the original graph:
(source, A) to (u, A) with the same weight.(source, A) to (u, B) with the weight in the new graph minus the weight of N1.(source, A) to (u, C) with the weight in the new graph minus the weight of N2.(source, A) to (u, D) with the weight in the new graph minus the weights of N1 and N2.
Since the new graph has 4V vertices and 4E - 2 edges, the worst-case performance of Dijkstra's algorithm is O((4E - 2) + 4V log 4V), which simplifies to O(E + V log V) as required.
To ensure that a shortest path in the new graph corresponds to a genuine path in the original graph, it remains to be proved that a path from e.g. (source, A) to (u, B) will not use two copies of the same edge from the original graph. That is quite easy to show, but I'll leave it to you as something to think about.
令 G(V,E) 为具有边长的有向加权图，其中除两条边的边长为负外，所有边长均为正。给定一个固定的顶点 s，给出一个算法在 O(e + v log(v)) 时间内计算从 s 到任何其他顶点的最短路径。
我的作品：
我正在考虑使用 Johnson 算法的重新加权技术。然后，运行 Belford Algo 一次并应用 Dijkstra v 次。这将使我的时间复杂度为 O(v^2 log v + ve)。 这是标准的全对最短问题，因为我只需要一个顶点 - 我的时间复杂度将是 O(v log v + e) 对吗？
For this kind of problem, changing the graph is often a lot easier than changing the algorithm. Let's call the two negative-weight edges N1 and N2; a path by definition cannot use the same edge more than once, so there are four kinds of path:
- A. Those which use neither N1 nor N2,
- B. Those which use N1 but not N2,
- C. Those which use N2 but not N1,
- D. Those which use both N1 and N2.
So we can construct a new graph with four copies of each node from the original graph, such that for each node u in the original graph, (u, A), (u, B), (u, C) and (u, D) are nodes in the new graph. The edges in the new graph are as follows:
- For each positive weight edge
u-vin the original graph, there are four copies of this edge in the new graph,(u, A)-(v, A)...(u, D)-(v, D). Each edge in the new graph has the same weight as the corresponding edge in the original graph. - For the first negative-weight edge (N1), there are two copies of this edge in the new graph; one from layer A to layer B, and one from layer C to layer D. These new edges have weight 0.
- For the second negative-weight edge (N2), there are two copies of this edge in the new graph; one from layer A to layer C, and one from layer B to layer D. These new edges have weight 0.
Now we can 运行 any standard single-source shortest-path problem, e.g. Dijkstra's algorithm, just once on the new graph. The shortest path from the source to a node u in the original graph will be one of the following four paths in the new graph, whichever corresponds to a path of the lowest weight in the original graph:
(source, A)to(u, A)with the same weight.(source, A)to(u, B)with the weight in the new graph minus the weight of N1.(source, A)to(u, C)with the weight in the new graph minus the weight of N2.(source, A)to(u, D)with the weight in the new graph minus the weights of N1 and N2.
Since the new graph has 4V vertices and 4E - 2 edges, the worst-case performance of Dijkstra's algorithm is O((4E - 2) + 4V log 4V), which simplifies to O(E + V log V) as required.
To ensure that a shortest path in the new graph corresponds to a genuine path in the original graph, it remains to be proved that a path from e.g. (source, A) to (u, B) will not use two copies of the same edge from the original graph. That is quite easy to show, but I'll leave it to you as something to think about.