Skip to content
TheChatArchiveThe Chat Archive
GPT 5.1· openaiHugging Face Frontier Reasoning Traces

Create an algorithm to find the shortest path in a weighted graph with negative weights…

  1. User

    Create an algorithm to find the shortest path in a weighted graph with negative weights (Bellman-Ford).

  2. 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

    1. Initialize distances:
      • dist[s] = 0
      • dist[v] = +∞ for all other vertices
    2. Relax all edges repeatedly:
      • Repeat |V| − 1 times:
        • For every edge (u, v) with weight w:
          • If dist[u] + w < dist[v], update dist[v] and pred[v].
    3. 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 s to some target t when 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 dist and pred

    This algorithm works when edges can have negative weights and correctly detects negative-weight cycles reachable from the source.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.