1. The problem

In a directed weighted graph G = (V, E), the weight of a path is the sum of its edge weights. Given a source s, we want the best weight for each reachable vertex v and, through predecessors, a path attaining it.

2. The shared operation: relax an edge

Keep an estimate d[v] of the shortest cost from s to v: d[s] = 0 and d[v] = +∞ for every other vertex. If a known route to u followed by edge u → v improves v, update its distance and predecessor.

Also set prev[v] = u. To recover the route to t, follow predecessors from t back to s and reverse the sequence. If d[t] = +∞, t is unreachable.

3. Dijkstra: nonnegative weights

Dijkstra repeatedly chooses the unsettled vertex with the smallest estimate, then relaxes its outgoing edges. Every reachable edge must have weight ≥ 0: otherwise a later route could improve an already settled vertex.

d[s] = 0; every other d[v] = +∞; prev[v] = undefined
push (0, s) into a min-priority queue
while the queue is not empty:
    pop (cost, u)
    if cost ≠ d[u]: continue  // stale entry
    for every edge u → v of weight w:
        if d[u] + w < d[v]:
            d[v] = d[u] + w; prev[v] = u
            push (d[v], v)

Example: s → a (4), s → b (1), b → a (2), a → t (1), b → t (7). The valid extraction order is s, b, a, t. From s we get a = 4 and b = 1; from b we improve a to 3 and find t = 8; from a we improve t to 4.

The shortest route to t is s → b → a → t with weight 1 + 2 + 1 = 4. The greedy choice is safe because appending nonnegative edges cannot produce a later cheaper route to an extracted vertex.

4. Bellman–Ford: negative weights and cycles

Bellman–Ford relaxes all edges for |V| − 1 passes. After pass k, estimates are optimal for paths using at most k edges. A simple path has at most |V| − 1 edges, so these passes suffice when no reachable negative cycle exists.

d[s] = 0; every other d[v] = +∞
repeat |V| − 1 times:
    for every edge u → v of weight w:
        if d[u] is finite and d[u] + w < d[v]:
            d[v] = d[u] + w; prev[v] = u
    if no estimate changed: stop the passes
for every edge u → v of weight w:
    if d[u] is finite and d[u] + w < d[v]:
        report a reachable negative cycle

Example with a negative edge: s → a (4), s → b (5), a → t (2), b → t (6), b → a (−3). Scanning edges in this order, the first pass gives a = 2 and t = 6; the second improves t to 4. The result is s → b → a → t, weight 5 − 3 + 2 = 4. The version of Dijkstra that settles extracted vertices would settle a at cost 4 too early.

For example, s → a (1), a → b (−2), b → a (1), b → t (2): a → b → a weighs −1. Repeating it before reaching t makes the cost to a, b and t unbounded below.

5. Longest paths: the linear-time case

In a DAG (directed acyclic graph), every path is simple. Compute a topological order, set L[s] = 0 and L[v] = −∞ for all other vertices, then process vertices in that order. For each edge u → v set L[v] = max(L[v], L[u] + w(u,v)) if L[u] is finite. Save the predecessor whenever the estimate improves.

This also works with negative weights: acyclicity is the essential condition. In the same DAG, replacing max with min and −∞ with +∞ computes shortest paths in O(|V| + |E|).

The longest route is s → a → b → t, weight 3 + 4 + 5 = 12. On general graphs, negating weights and applying Bellman–Ford solves the walk variant only if no positive cycle is reachable; it does not solve the longest simple path problem, which is NP-hard in general.

6. Which algorithm?

Bounds assume adjacency lists and simple graphs; Dijkstra uses a binary priority queue. Times include the vertices even for disconnected graphs. Bellman–Ford can stop early when a pass changes nothing, but its worst case remains O(|V| + |V|·|E|).

A minimum spanning tree connects every vertex at the lowest total network cost; it does not guarantee shortest routes from s. See minimum spanning tree.

7. Mistakes and exercises

• Using Dijkstra with negative edges: even one edge can invalidate a settled choice.
• Confusing +∞ and −∞: the former initializes shortest paths, the latter longest paths in DAGs.
• Ignoring reachability: a negative cycle in a component unreachable from s does not affect distances from s.