如何高效验证有向图中各顶点的最短路径估计值d[v]？

Great question! Comparing against a full Bellman-Ford run is indeed overkill here—we can validate the given d[v] values in O(V + E) time (linear time, much faster than Bellman-Ford's O(VE)) by leaning on core shortest path properties. Here's a step-by-step breakdown:

Step 1: Check Non-Negotiable Invariants #

First, confirm two necessary conditions (if either fails, the d[v] values are definitely invalid):

• Source Vertex Check: Ensure d[s] == 0—unless s is part of a reachable negative cycle. If s is in a negative cycle, d[s] must be -∞ (since there's no finite shortest path from s to itself).
• Triangle Inequality for All Edges: For every directed edge u → v with weight w, verify that d[v] ≤ d[u] + w. This is the core property of shortest paths: taking any edge from u to v can't give a shorter path to v than the given d[v]. If any edge violates this, you can immediately conclude the d[v] values are wrong.

Step 2: Validate Reachability and Negative Cycle Consistency #

Passing Step 1 tells us d[v] is a valid lower bound for the shortest path from s to v, but we need to make sure it's the tightest possible bound (or correctly marked as -∞ for vertices with no finite shortest path):

1. Build the Equality Subgraph: Create a subgraph H that includes only edges where d[v] == d[u] + w. These edges represent potential shortest path edges—if d[v] is valid, there must be a path from s to v using only these edges.
2. Check Finite Distances: For every vertex v with a finite d[v]:
   • Run a BFS or DFS starting from s on H—if v isn't reachable via this subgraph, there's no path whose total weight equals d[v], so the given distance is invalid.
3. Check Infinite (Negative) Distances: For every vertex v marked with d[v] == -∞:
   • First, v must be reachable from s in the original graph G (if it's not reachable, d[v] should be ∞, not -∞).
   • Second, v must be able to reach a negative cycle in G (since only then can you loop the cycle infinitely to get arbitrarily small distances). To verify this efficiently:
     • Use BFS/DFS on G to find all vertices reachable from s (call this set R).
     • Build the reverse graph G' (flip all edge directions).
     • Find all vertices in G that are part of a negative cycle (run Bellman-Ford once on s—vertices that can still be relaxed after V-1 iterations are in or can reach a negative cycle).
     • Run BFS/DFS on G' from these negative cycle vertices to find all vertices that can reach a negative cycle. Any v marked -∞ must be in this set and in R; conversely, any vertex in both sets must be marked -∞.

Why This Is Better Than Bellman-Ford #

Bellman-Ford computes all shortest paths from scratch, which is O(VE). This approach, by contrast, leverages the given d[v] values to skip redundant computations, resulting in linear time complexity—perfect for large graphs where Bellman-Ford would be too slow.

内容的提问来源于stack exchange，提问作者Ori Netanel Ben-Zaken