CSCE 411 Lecture 21

Lecture Slides

« previous | Monday, October 15, 2012 | next »

Bellman-Ford Algorithm

Similar to Dijkstra's Algorithm, but can handle negative edge weights (and can even detect negative weight cycles if they exist).

Basic Idea:

• Consider each edge $(u,v)$ and see if $u$ offers a cheaper path from $s$ (compare $d_{v}$ to $d_{u}+w(u,v)$.
• Repeat process $|V|-1$ times to ensure that accurate information propagates from $s$, no matter what order the edges are considered.

def bellman_ford graph, source
  # initialization
  graph.each_vertex {|v| v.distance = Float::INFINITY; v.parent = nil }
  source.parent = source
  source.distance = 0

  # main body
  1.upto(graph.vertices.size - 1) do
    edge_relaxed = false

    graph.each_edge do |edge|
      if edge.start.distance + edge.weight < edge.end.distance
        edge.end.distance = edge.start.distance + edge.weight
        edge.end.parent = edge.start
        edge_relaxed = true
      end
    end

    # optimization
    break unless edge_relaxed
  end

  # check for negative weight cycles
  graph.each_edge do |edge|
    if edge.start.distance + edge.weight < edge.end.distance
      throw "Negative weight cycle detected!"
    end
  end
end

Correctness

Assume no negative-weight cycles

Lemma: $d_{v}$ is never an underestimate of the actual shortest path distance from $s$ to $v$.

Lemma: If there is a shortest $s\to v$ path containing at most $i$ edges, then after iteration $i$ of the outer loop, $d_{v}$ is at most the shortest path distance from $s$ to $v$.