# 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