Bellman-Ford Shortest-Path Algorithm: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
 
(2 intermediate revisions by the same user not shown)
Line 14: Line 14:


=Overview=
=Overview=
An algorithm that can compute shortest path in graphs with [[Graph_Concepts#Negative_Length_Edge|negative length edges]]. The running time complexity is O(mn).
A dynamic programming algorithm that can compute shortest path in graphs with [[Graph_Concepts#Negative_Length_Edge|negative length edges]].
 
There are n<sup>2</sup> subproblems, and we might spend more than linear time for each subproblem: we have to do brute force search through a list of candidates that might be super-constant: each arc that comes into the vertex v provides a candidate for what the correct solution to the subproblem may be, and the number of candidates is proportional to the degree of vertex v. The running time is O(mn). In a sparse graph, m=O(n), and in a dense graph is O(n<sup>2</sup>).

Latest revision as of 02:44, 30 November 2021

External

Internal

Overview

A dynamic programming algorithm that can compute shortest path in graphs with negative length edges.

There are n2 subproblems, and we might spend more than linear time for each subproblem: we have to do brute force search through a list of candidates that might be super-constant: each arc that comes into the vertex v provides a candidate for what the correct solution to the subproblem may be, and the number of candidates is proportional to the degree of vertex v. The running time is O(mn). In a sparse graph, m=O(n), and in a dense graph is O(n2).