Bellman-Ford: Difference between revisions
Jump to navigation
Jump to search
(Created page with "Category:Algorithm Category:Main Algorithm '''Algorithmic problem:''' All pairs shortest paths '''Prerequisites:''' '''Type of algorithm:''' loop '''Auxiliary data...") |
(No difference)
|
Revision as of 09:51, 6 October 2014
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.