Talk:Bellman–Ford algorithm: Difference between revisions

Revision as of 11:44, 3 September 2011

Revision as of 11:54, 3 September 2011

Line 53:

Are we sure this is the Bellman-Ford algorithm and not the generic labeling method? There's a source in which Bellman-Ford is described as an optimization of the labeling algorithm using a FIFO queue. (http://avglab.com/andrew/pub/neci-tr-96-029.ps). This is just a question, I am right now confused because of different sources describing a very different algorithm.

[[User:Vexorian|Vexorian]] ([[User talk:Vexorian|talk]]) 13:01, 17 January 2009 (UTC)

FIFO Bellman-Ford is an optimization for the Bellman-Ford algorithm.

The generic relabel-relax method is defined differently, informal description follows:

'''generic relabel-relax''':

''// I Initialize''

'''for each''' vertex v '''in''' vertices:

'''if''' v '''is''' source '''then''' v.distance := 0

'''else''' v.distance := '''infinity'''

v.predecessor := '''null'''

''// II Loop''

'''while''' (edge uv that can be relaxed) '''exists''':

relax (u, v, λ)

== Undefined Terms ==