Bellman-Ford
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...")
Algorithmic problem: All pairs shortest paths Prerequisites: Type of algorithm: loop Auxiliary data:
- 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.
- 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.