Shortest Paths

Summary

There are two main ways to find shortest paths between two vertices using Dynamic Programming techniques. They can both be used to find Negative Weight Cycles, but there is some nuance between the two.

Contents

• Problem Setup
• Negative Weight Cycle
• Single Source
  • Recurrence
  • Psuedcode
• We look at all the edges INTO z by using the adj. list of the reverse
• graph
  • Finding Negative Weight Cycles
• All Pairs
  • Recurrence
  • Psuedocode
  • Finding Negative Weight Cycles
• Comparing Algorithms

Problem Setup

Given a directed graph G=(V,E) with edge weights W

Fix s in V

for all z in V, dist(z) = length of shortest path from s to Z

Negative Weight Cycle

$a \rightarrow e \rightarrow b \rightarrow a$ is a negative weight cycle becuase adding up the weights gives us a negative number.

When a graph has a NWC, the shortest path problem is no longer well defined.

So when given a graph, we either want to find a negative weight cycle or find dist(z) for all z in V

Single Source

Given a directed graph G with edge weights and a start vertex s (assume no negative weigh cycles), find the shortest path from s to z.

Since the path length is at most n-1 edges:

$\text{For } 0 \le i \le n-1 & z \in V:$

$\text{let } D(i,z) = \text{ length of shortest path from } s \text{ to } z \text{ using } \le i \text{ edges.}$

Recurrence

$D(0,s) = 0 & \forall z \ne s, D(0,z) = \infty$

$D(i,z) = \text{ shortest path } s \leadsto z \text{ using } \le i \text{ edges}$

$D(i,z) = \min{\left{\displaystyle\min_{y : y \leadsto z \in E}{\left{D(i-1,y) + w(y,z)\right} }, D(i-1,z)\right}}$

Psuedcode

Bellman-Ford(G,s,w):
  for all z in V, D(0,z) = inf
  D(0,s) = 0
  for i = 1 -> n-1:
    for all z in V:
      D(i,z) = D(i-1,z)

      # We look at all the edges INTO z by using the adj. list of the reverse
      # graph
      for all (y,z) in E:
        if D(i,z) > D(i-1,y) + w(y,z)
          then D(i,z) = D(i-1,y) + w(y,z)

  return (D(n-1,*))

O(nm) (slower than Dijkstra’s)

Finding Negative Weight Cycles

n-1 = 5, but we’ll do n iterations anyway

If any nodes are different from n to n-1, we have a cycle. We can find the cycle by backtracking and looking at which nodes are different in each iteration.

Bellman-Ford finds the shortest path from a single vertex to every other node, allowing for negative weights, and detecting negative weight cycles, in O(nm) time.

All Pairs

Given a directed graph G, with edge weights w,

$\forall{(y,z) \in V}, \text{ let } dist(y,z) = \text{ length of shortest path } y \leadsto z$

Easy approach is to run Bellman-Ford for all s in V, $O(n^2m) \text{ where } m \le n^2$

Floyd-Warshall $O(n^3)$

$\text{let } V = { 1, 2, \ldots, n }$

Condition on intermediate vertices (i.e. use a prefix of V)

$\text{For } 0 \le i \le n & 1 \le s, t \le n$

$\text{let } D(i,s,t) = \text{ length of shortest path } s \leadsto t$

$\text{using a subet of } { 1, \ldots, i } \text{ as intermediate vertices}$

Recurrence

$D(0,s,t) = \begin{cases}w(s,t) & \text{ if } \overrightarrow{st} \in E \ \infty & \text{ otherwise} \end{cases}$

$D(i,s,t) = \begin{cases}D(i-1,s,t) & \text{ if } i \not\in \mathcal{P} \ D(i-1,s,i) + D(i-1,i,t) & \text{ if } i \in \mathcal{P} \end{cases}$

$D(i,s,t) = \min{{ D(i-1,s,t), D(i-1,s,i) + D(i-1,i,t) }}$

Psuedocode

Floyd_Warshall(G,w):
  for s = 1 -> n:
    for t = 1 -> n:
      if (s,t) in E:
        D(0,s,t) = w(s,t)
      else:
        D(0,s,t) = inf
  for i = 1 -> n:
    for s = 1 -> n:
      for t = 1 -> n:
        D(i,s,t) = min(D(i-1,s,t), D(i-1,s,i) + D(i-1,i,t))

  return D(n,*,*)

$O(n^3)$

This assumes no negative weight cycles

Finding Negative Weight Cycles

Check if $\exists y \in V : D(n,y,y) < 0$

Comparing Algorithms

Bellman-Ford only find NWC that are reachable from starting vertex

Floyd-Warshall finds all NWC