The Bellman-Ford algorithm solves the single-source shortest paths problem in more general settings.
- Unlike Dijkstra’s algorithm, it allows edges of negative length. However, it takes a much longer time.
- Unlike Dijkstra’s algorithm that adopts the greedy policy, the Bellman-Ford algorithm adopts the Dynamic Programming technique, progressively decreasing the estimate of v. d the distance from s to node v until the estimate is precise
The algorithm returns true if and only if the graph does not contain any negative cycles that are reachable from the source.
Because we want to obtain the minimum value of weight of path, so this path can be |V| vertices long, which means that we need to do |V| iterations.
时间复杂度是O（V*E）
Single-Source Shortest Paths in DAGs
For a directed acyclic graph (DAG), we can relax the edges according to the topological order of their start vertices, from left to right.
Determine the topological order of each vertex v ∈ V , using the DFS technique.
The time complexity of algorithm DAG Shortest Paths is O(|V|+|E|).
网友评论