Lecture18_ShortestPaths2
Tuesday, October 20, 2020
4:21 PM
Unweighted graph
Suppose that w(u, v) = 1 for all (u, v) ∈ E. Can Dijkstra’s algorithm be improved?
The PQ we have does not have to be a true PQ. Reason: whenever we found a new improved path, we change the key value or the distance. Therefore, this component won’t have dramatic change.
➢Use a simple FIFO queue instead of a priority queue. Correctness of BFS
Running time: O(V + E)
• Works for all edge weight are same
• Limitation of Dijkstra’s algorithm? No negative edge weight.
Determine eight negative cycle exist
Question: remove negative edge weight by adding x to all edge weight, where -x is the smallest edge weight in the graph.
➢Do we still have the same problem?? Do they have same shortest path? ➢Design a counter example showing that this idea would not work
No! the problem changes!! The shortest path changes!!
The addition may affect the path multiple times
• This modification based on for each path, we add number of edges times x to the
shortest path.
Negative-weight cycles
If a graph G = (V, E) contains a negative weight cycle, then some shortest paths may not exist.
Bellman-Ford algorithm: Finds all shortest-path lengths from a source s ∈ V to all v ∈ V or determines that a negative-weight cycle exists.
• Figure out if there exist negative cycles
Analysis of Algorithms Page 1
// do relaxation when found better path
How many times we do relaxation? In which order we do?
Does not matter (matters for Dijkstra)
N – 1 pass maximum. (at most n – 1 edges for n vertices )
After n -1 relaxations, if it still can do relaxations, then there is negative cycle.*
• One node can be update more than one time in single iteration • If one whole pass doesn’t change any ting, done
Correctness:
Theorem. If G = (V, E) contains no negative weight cycles, then after the Bellman-Ford algorithm executes, d[v] = δ(s, v) for all v ∈ V.
Corollary. If a value d[v] fails to converge after |V| – 1 passes, there exists a negative-weight cycle in G reachable from s.
Analysis of Algorithms Page 2