Dijkstra's Algorithm

Statement

Consider a digraph D = (N, A) with non-negative weights w ∈ ℝ_≥0^A and a node s. Dijkstra's algorithm finds a tree of shortest dipaths rooted from s. We assume all nodes are reachable from s.

Pseudocode

Dijkstra(D = (N, A), w ∈ ℝ≥0A, s ∈ N)
1:   for all u ∈ N do
2:       y(u) := ∞
3:       p(u) := undefined
4:   end for
5:   y(s) := 0
6:   Q := N   // Set of unfinalized nodes
7:   while Q ≠ ∅ do
8:       u := argmin{ y(v) : v ∈ Q }
9:       remove u from Q
10:      for all arcs (u, v) ∈ A do
11:          if y(v) > y(u) + wuv then
12:              y(v) := y(u) + wuv
13:              p(v) := u
14:          end if
15:      end for
16:  end while
17:  return (y, p)
    

• y(u): Current shortest-path estimate from s to u
• p(u): Predecessor of u in the shortest path
• Initially, y(u) = ∞ for all u ≠ s, y(s) = 0
• At each step, finalize the node with the smallest label y(u)
• Relax outgoing arcs of u: update neighbors v if a shorter path is found via u

Correctness

Dijkstra's algorithm is correct under the assumption that w(e) ≥ 0 for all e ∈ A. When a node u is selected (finalized) at line 8, y(u) is the length of the shortest s-u dipath.

• Sketch of proof:
  • The algorithm always selects a node u with the smallest temporary label. If there were a shorter path to u through another node not yet finalized, this would contradict the minimality of y(u).
  • Since all edge weights are non-negative, no shorter path to u can be found after u is finalized.

Note: The algorithm fails if negative arc weights are allowed.

Time Complexity

• Using binary heap: O((|N| + |A|) log |N|)
• Using Fibonacci heap: O(|A| + |N| log |N|)

Topological Ordering and Shortest Paths in Acyclic Graphs

Topological Ordering

Let D = (N, A) be a directed acyclic graph (DAG). A topological ordering of D is a bijection π : N → {1, ..., |N|} such that for every arc (u, v) ∈ A, π(u) < π(v).
That is, every node comes before all its out-neighbors in the ordering.

• A digraph admits a topological ordering if and only if it is acyclic.
• Topological orderings are not necessarily unique.

Algorithm: Finding a Topological Order

Topological-Order(D = (N, A))
1:  L := empty list (will contain the order)
2:  S := { u ∈ N : u has in-degree 0 }
3:  while S ≠ ∅ do
4:      remove a node u from S
5:      append u to L
6:      for each (u, v) ∈ A do
7:          remove arc (u, v) from A
8:          if v now has in-degree 0 then
9:              insert v into S
10:     end for
11: end while
12: if any arcs remain in A then
13:     return "Graph has a cycle"
14: else
15:     return L
    

• S: set of nodes with no incoming arcs
• L: resulting topological order (sequence of nodes)
• If after the loop there are arcs left, the graph contains a cycle

Shortest Path Algorithm for Acyclic Graphs (DAGs)

If D = (N, A) is a DAG with weights w ∈ ℝ^A, and s ∈ N is a source, we can compute shortest paths from s to all nodes in O(|N| + |A|) time.

Acyclic-Shortest-Paths(D = (N, A), w ∈ ℝA, s ∈ N)
1:  Compute a topological order π of D
2:  for all u ∈ N do
3:      y(u) := ∞
4:      p(u) := undefined
5:  end for
6:  y(s) := 0
7:  for k = 1 to |N| do
8:      u := node with π(u) = k
9:      for all (u, v) ∈ A do
10:         if y(v) > y(u) + wuv then
11:             y(v) := y(u) + wuv
12:             p(v) := u
13:         end if
14:     end for
15: end for
16: return (y, p)
    

• Visit nodes in topological order.
• At each step, relax all outgoing arcs from the current node.
• This computes shortest paths from s even if negative weights are present (as long as the graph is acyclic).

Correctness

• When visiting a node u in topological order, all possible predecessors of u have already been processed and their shortest distances computed.
• As there are no cycles, this ensures that when y(u) is updated, all previously needed information is already correct.

Remark: The acyclic shortest path algorithm works for any weights (even negative), provided the graph is acyclic.

Dantzig's Algorithm

Statement

Let D = (N, A) be a directed graph with arc weights w ∈ ℝ^A and a source node s ∈ N. Dantzig's algorithm computes shortest path distances from s to all other nodes, as long as there are no negative-weight dicycles in D.

• Arc weights may be negative.
• Algorithm detects negative-weight cycles if present.

Pseudocode

Dantzig(D = (N, A), w ∈ ℝA, s ∈ N)
1:  for all u ∈ N do
2:      y(u) := ∞
3:      p(u) := undefined
4:  end for
5:  y(s) := 0
6:  Q := {s}   // Set of nodes to process
7:  while Q ≠ ∅ do
8:      remove a node u from Q
9:      for all (u, v) ∈ A do
10:         if y(v) > y(u) + wuv then
11:             y(v) := y(u) + wuv
12:             p(v) := u
13:             if v ∉ Q then
14:                 add v to Q
15:             end if
16:         end if
17:     end for
18: end while
19: if any label y(v) was updated more than |N| - 1 times then
20:     return "Graph contains a negative-weight dicycle"
21: else
22:     return (y, p)
    

• y(u): Current estimate of the shortest path distance from s to u
• p(u): Predecessor of u in the shortest path
• Q: Set of nodes whose outgoing arcs need to be checked (may be implemented as a queue or set)

Explanation

• The algorithm starts by initializing all distances to infinity except for the source node.
• Nodes whose labels have changed are added to Q.
• While Q is not empty, remove a node, and for each outgoing arc, "relax" the neighbor.
• If a neighbor's distance decreases, it is (re)added to Q for further processing.
• If any node's label is updated more than |N| - 1 times, a negative-weight cycle exists (since the shortest path from s to any node should have at most |N| - 1 arcs).

Correctness

• If D contains no negative-weight dicycles, the algorithm computes the shortest path distances from s to all nodes.
• Every time a label y(u) is decreased, a strictly shorter path from s to u is found.
• Since the shortest path can use at most |N| - 1 arcs, more updates imply a negative-weight dicycle.

Remark: Dantzig's algorithm is a generic label-correcting method; special cases include the Bellman-Ford and queue-based SPFA algorithms.

Time Complexity

• In the worst case, O(|N||A|), but often faster in practice with an appropriate queue implementation.

Bellman-Ford Algorithm and Finding Negative Dicycles

Statement

Let D = (N, A) be a directed graph with arc weights w ∈ ℝ^A and a source node s ∈ N. The Bellman-Ford algorithm computes the shortest path distances from s to every node. The algorithm detects the existence of negative-weight dicycles (directed cycles) if present.

• Arc weights may be negative.
• Returns either shortest paths or a certificate of a negative dicycle.

Notation

• For each i = 0, 1, ..., |N|-1, define
  y⁽ⁱ⁾(v) = length of the shortest s-v dipath in D using at most i arcs (if no such dipath exists, set y⁽ⁱ⁾(v) = ∞).
• y⁽⁰⁾(s) = 0; y⁽⁰⁾(v) = ∞ for v ≠ s.
• At each step, y⁽ⁱ⁾(v) is updated as
  y⁽ⁱ⁾(v) = min{ y^(i-1)(v), min_(u,v)∈A[ y^(i-1)(u) + w_uv ] }

Pseudocode

Bellman-Ford(D = (N, A), w ∈ ℝA, s ∈ N)
1:  y(0)(s) := 0
2:  y(0)(u) := ∞ for all u ∈ N, u ≠ s
3:  p(u) := undefined for all u ∈ N
4:  for i = 1 to |N| - 1 do
5:      for all v ∈ N (in any order) do
6:          y(i)(v) := min { y(i-1)(v), min(u,v)∈A [ y(i-1)(u) + wuv ] }
7:          if y(i)(v) < y(i-1)(v) then
8:              Let u ∈ N such that y(i)(v) = y(i-1)(u) + wuv
9:              p(v) := u
10:         end if
11:     end for
12: end for
13: for all (u, v) ∈ A do
14:     if y(|N|-1)(v) > y(|N|-1)(u) + wuv then
15:         return "D contains a negative-weight dicycle"
16:     end if
17: end for
18: return (y(|N|-1), p)
    

• y⁽ⁱ⁾(v): Length of the shortest s-v dipath with at most i arcs.
• p(v): Predecessor of v in the shortest path.
• The main loop (lines 4-12) performs |N|-1 relaxations for all nodes.
• The check in lines 13-17 determines if a negative dicycle exists.

Finding a Negative Dicycle (if exists)

• If after |N|-1 rounds, there is an arc (u, v) with y^(|N|-1)(v) > y^(|N|-1)(u) + w_uv, then a negative dicycle exists and can be found as follows:
• Tracing back predecessors: From v, repeatedly apply p(⋅) for up to |N| steps to find a repeated node, indicating a cycle.
• This cycle will be a negative-weight dicycle.

Find-Negative-Dicycle(p, v)
1:  Mark all nodes as unvisited
2:  for i = 1 to |N| do
3:      v := p(v)
4:  end for
5:  start := v
6:  C := [start]
7:  v := p(start)
8:  while v ≠ start do
9:      Append v to C
10:     v := p(v)
11: end while
12: return C   // C is the negative-weight dicycle
    

Correctness

• Claim 1. For every integer i = 0, 1, ..., n-1 and every v ∈ N, y⁽ⁱ⁾(v) is the length of the shortest s–v dipath in D using at most i arcs (and ∞ if no such dipath exists).
• Proof.
  Base case (i = 0): The only dipath from s with 0 arcs is the trivial path at s itself, so y⁽⁰⁾(s) = 0 and y⁽⁰⁾(v) = ∞ for v ≠ s.
  Inductive step: Assume the claim holds for i-1. For y⁽ⁱ⁾(v), there are two possibilities:
  (a) The shortest s–v dipath uses ≤ i – 1 arcs (so y^(i-1)(v) is optimal);
  (b) Otherwise, it uses exactly i arcs, i.e., it consists of an s–u dipath of ≤ i–1 arcs followed by arc (u,v), for some u; the total length is y^(i-1)(u) + w_uv.
  The algorithm sets y⁽ⁱ⁾(v) = min { y^(i-1)(v), min_(u,v)∈A[ y^(i-1)(u) + w_uv ] }, so the claim follows by induction.
• Claim 2. If D has no negative-weight dicycles, then for every v ∈ N, the shortest s–v dipath is a simple path with at most n – 1 arcs. Thus, y^(n-1)(v) is the length of the shortest s–v dipath.
• Proof.
  If a dipath from s to v contains a repeated node, it contains a dicycle. If that dicycle has negative weight, the path is not optimal (since the total length could be made arbitrarily small by repeating it). In the absence of negative-weight dicycles, the shortest dipath can always be taken as simple (no repeated nodes), and thus uses at most n – 1 arcs. By Claim 1, y^(n-1)(v) is the length of the shortest s–v dipath.
• Claim 3. If D contains no negative-weight dicycles, the Bellman-Ford algorithm returns the shortest path lengths y^(n-1)(v) for every v ∈ N. If a negative dicycle exists, the algorithm detects it.
• Proof.
  By Claim 2, after n – 1 rounds, y^(n-1)(v) equals the length of the shortest s–v dipath for all v if there are no negative dicycles. If, after the main loop, there exists an arc (u, v) such that y^(n-1)(v) > y^(n-1)(u) + w_uv, then some path can still be improved, which implies the existence of a negative-weight dicycle (otherwise, by Claim 2, all optimal paths use ≤  arcs and cannot be further improved). Thus, the algorithm correctly finds shortest path distances or detects a negative dicycle.

Time Complexity

• Main loop: O(|N||A|)
• Negative cycle check: O(|A|)
• Extracting the negative dicycle: O(|N|)