Bellman-Ford Shortest-Path Algorithm: Difference between revisions
Jump to navigation
Jump to search
| (3 intermediate revisions by the same user not shown) | |||
| Line 11: | Line 11: | ||
* [[Dynamic_Programming#Canonical_Use|Dynamic Programming]] | * [[Dynamic_Programming#Canonical_Use|Dynamic Programming]] | ||
* [[Floyd-Warshall Algorithm]] | * [[Floyd-Warshall Algorithm]] | ||
* [[Johnson's Algorithm]] | |||
=Overview= | =Overview= | ||
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
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/x0YZd/single-source-shortest-paths-revisted
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/g8N36/optimal-substructure
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/9YeyY/the-basic-algorithm-i
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/WhILJ/the-basic-algorithm-ii
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/AB5wH/detecting-negative-cycles
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/TrNPq/a-space-optimization
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).