Create an algorithm to find the shortest path in a weighted graph with negative weights…
- User
Create an algorithm to find the shortest path in a weighted graph with negative weights (Bellman-Ford).
- Assistant
Formulating algorithm steps
The user is asking for an algorithm to find the shortest path in a weighted graph with negative weights using the Bellman-Ford approach. It seems they’d like an explanation along with pseudocode and the algorithm steps. I’ll ensure it’s concise but still includes details like input format, initialization, and the edge relaxation process. I could also mention negative cycle detection and possibly include a brief example. Let's outline clear steps and pseudocode! Here is the Bellman–Ford algorithm to find single‑source shortest paths in a weighted directed graph that may contain negative edge weights (but no negative cycles reachable from the source).
Problem Setting
Input:
- A directed graph ( G = (V, E) )
- Edge list ( E ) where each edge ( (u, v) ) has weight ( w(u, v) ) (can be negative)
- A source vertex ( s \in V )
Output:
dist[v]: shortest distance from ( s ) to every vertex ( v ) (if it exists)pred[v]: predecessor of ( v ) on a shortest path from ( s ) (for path reconstruction)- Indication if a negative-weight cycle is reachable from ( s )
High-Level Idea
- Initialize distances:
dist[s] = 0dist[v] = +∞for all other vertices
- Relax all edges repeatedly:
- Repeat |V| − 1 times:
- For every edge (u, v) with weight w:
- If
dist[u] + w < dist[v], updatedist[v]andpred[v].
- If
- For every edge (u, v) with weight w:
- Repeat |V| − 1 times:
- Check for negative-weight cycles:
- If you can still relax any edge, then a negative cycle is reachable from the source.
Pseudocode
BellmanFord(V, E, w, s): # V: set of vertices # E: set of directed edges (u, v) # w(u, v): weight of edge (u, v) # s: source vertex # 1. Initialization for each vertex v in V: dist[v] ← +∞ pred[v] ← NIL dist[s] ← 0 # 2. Relax edges |V| - 1 times for i from 1 to |V| - 1: updated ← false for each edge (u, v) in E: if dist[u] ≠ +∞ and dist[u] + w(u, v) < dist[v]: dist[v] ← dist[u] + w(u, v) pred[v] ← u updated ← true # Optional early stopping: if no update in this pass, we can stop if not updated: break # 3. Check for negative-weight cycles reachable from s for each edge (u, v) in E: if dist[u] ≠ +∞ and dist[u] + w(u, v) < dist[v]: # Negative cycle detected return ("NEGATIVE_CYCLE", dist, pred) return ("OK", dist, pred)
Reconstructing a Shortest Path
To get the actual path from
sto some targettwhen result is"OK":ReconstructPath(pred, s, t): path ← empty list current ← t while current ≠ NIL: prepend current to path if current = s: break current ← pred[current] if first element of path ≠ s: # No path from s to t return "NO_PATH" else: return path
Complexity
- Time: ( O(|V| \cdot |E|) )
- Space: ( O(|V|) ) for
distandpred
This algorithm works when edges can have negative weights and correctly detects negative-weight cycles reachable from the source.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.