9 - Graph Matching 5 Flashcards
What is all-pairs shortest paths?
What is Dijkstra’s algorithm?
- given a single source vertex s, it computes a shortest path from s to every other vertex in the graph
- it maintains a set S of vertices for which shortest path from s is known
- for each vertex v, it maintains a value d(v) representing the length of a shortest path from s to
- v passing only through vertices of S
- assume that wt(v,w) represents the weight of the edge (v,w)
- assume that adj(v) represents the adjacency list of vertex v
What is the pseudocode for Dijkstra’s algorithm?
Negative edge weights
Single-source shortest paths
- Alternative: Bellman-Ford algorithm
- given a single source vertex s, compute a shortest path from s to every other vertex in the graph
- algorithm works even if there are negative edge weights
- runs in O(nm) time, where m=|E|
- could use it for each source vertex in the graph to obtain all-pairs shortest paths - O(n2m) time
- If G is dense (i.e. |E|n2), Bellman-Ford algorithm is no better than O(n4)
- We will see an O(n3) algorithm
- the Floyd-Warshall algorithm
- based on dynamic programming
- assume there are no negative weight cycles
How to construct D*?
Alternative: Bellman-Ford algorithm
– given a single source vertex s, compute a shortest path from s to every other vertex in the graph
– algorithm works even if there are negative edge weights
– runs in O(nm) time, where m=|E|
– could use it for each source vertex in the graph to obtain all-pairs shortest paths - O(n2m) time
If G is dense (i.e. |E|n2), Bellman-Ford algorithm is no better than O(n4)
We will see an O(n3) algorithm
– the Floyd-Warshall algorithm
– based on dynamic programming
– assume there are no negative weight cycles
Key property of D*/dijktra’s algorithm
For k 0, Dk (i,j) contains the shortest path distance from vi to vj whose intermediate vertices (if any) belong to {v1, v2, …, vk}.
What is the Floyd - Warshall algorithm?
example algorithm execution
see slides
