Bellman-Ford

From Algowiki
Revision as of 09:51, 6 October 2014 by Cuozzo (talk | contribs) (Created page with "Category:Algorithm Category:Main Algorithm '''Algorithmic problem:''' All pairs shortest paths '''Prerequisites:''' '''Type of algorithm:''' loop '''Auxiliary data...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Algorithmic problem: All pairs shortest paths Prerequisites: Type of algorithm: loop Auxiliary data:

  1. A distance-valued [math]\displaystyle{ (n \times n) }[/math] matrix [math]\displaystyle{ M }[/math], where [math]\displaystyle{ n=|V| }[/math]. The eventual contents of [math]\displaystyle{ M }[/math] will be returned as the result of the algorithm.
  2. A distance-valued [math]\displaystyle{ (n \times n) }[/math] matrix [math]\displaystyle{ L }[/math], where [math]\displaystyle{ n=|V| }[/math]. This matrix represents the graph and the arc lengths and will not be changed throughout the algorithm. It is [math]\displaystyle{ L=M^1 }[/math] in the terminology of Section "Powers of distance matrices" on this page.