动态图插入边后单源最短路径更新的算法优化问询

Great question—this is a classic problem in dynamic graph algorithms, and the answer hinges on whether you're maintaining single-source shortest paths (SSSP) (from your fixed vertex v to all others) or all-pairs shortest paths (APSP). Let's break this down with practical optimizations and a rigorous proof for the worst-case scenario:

1. Optimizations for Single-Source Shortest Paths (No Need to Traverse All Node Pairs) #

Since you specifically care about updating paths starting from a fixed vertex v, the Floyd-Warshall-based all-pairs approach is overkill. You can optimize this drastically using precomputed SSSP information:

• Precomputation Step:

  1. Run Dijkstra (if your graph has non-negative edge weights) or Bellman-Ford once on the initial graph to get d(v, x): the shortest distance from v to every node x.
  2. If your graph has negative weights (but no negative cycles), precompute the reverse graph (flip all edge directions) and run SSSP from v to get d_rev(x, v): the shortest distance from any node x to v (useful for edge insertion edge cases).

• Edge Insertion Update:
  When inserting an edge e = (u, w) with weight c:

  1. First check if this edge directly improves the path from v to w: if d(v, w) > d(v, u) + c, update d(v, w) to d(v, u) + c.
  2. Then, use a priority queue (like in Dijkstra's algorithm) to propagate this update only to nodes that could benefit from it: add w to the queue, and for each node y adjacent to w, check if d(v, y) > d(v, w) + weight(w, y). If so, update d(v, y) and add y to the queue.
  3. This only processes nodes whose shortest paths could potentially be shortened by the new edge—no need to iterate over all n² node pairs.

• Time Complexity: Worst-case is O(m + n log n) (same as a single Dijkstra run), but in practice, it's much faster if the new edge only affects a small subset of nodes.

2. All-Pairs Shortest Paths: Worst-Case Requires O(n²) Time (Rigorous Proof) #

If you need to maintain all pairs of shortest paths (not just from v), then in the worst case, you cannot avoid checking all n² node pairs. Here's why:

Proof by Contradiction & Adversarial Graph Construction #

Suppose there exists an algorithm that can update APSP in o(n²) time after inserting an edge. This means the algorithm skips checking at least one node pair (x, y). We can construct a graph where this oversight leads to an incorrect result:

1. Initial Graph Setup:

   • Split n nodes into three sets: A (size k), B (size k), and two intermediate nodes u and v (so n = 2k + 2).
   • Add edges a → u with weight 1 for all a ∈ A, and edges v → b with weight 1 for all b ∈ B.
   • No edges exist between u and v, or between A and B, or within A/B.
   • Initial APSP distances: d(a, b) = ∞ for all a ∈ A, b ∈ B (no valid path exists).

2. Edge Insertion:
   Insert an edge (u, v) with weight 1 (a small, finite value).

3. Impact of the New Edge:
   Every node pair (a, b) now has a valid shortest path a → u → v → b with total weight 3, which is a massive improvement over the initial ∞. This affects k² = Ω(n²) node pairs.

If the algorithm skips even one (a, b) pair, it will leave d(a, b) as ∞ instead of updating it to 3, resulting in an incorrect APSP table. Thus, any correct algorithm must check all n² pairs in this worst-case scenario.

Conclusion for APSP #

Since we can construct adversarial graphs where every node pair's shortest path may be affected by a single edge insertion, the O(n²) time complexity is unavoidable for correct all-pairs updates.

3. Final Takeaways #

• SSSP (Your Use Case): Ditch the Floyd-Warshall all-pairs approach—use a priority queue-based relaxation to only update nodes affected by the new edge. This avoids traversing all n² pairs and is far more efficient.
• APSP: Worst-case requires O(n²) time, and no algorithm can beat this lower bound for correct updates.

内容的提问来源于stack exchange，提问作者Patel Parth