# 9 - Graph Matching 5 Flashcards

1
Q

What is all-pairs shortest paths?

A
2
Q

What is Dijkstra’s algorithm?

A
• 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
3
Q

What is the pseudocode for Dijkstra’s algorithm?

A
4
Q

Negative edge weights

A
5
Q

Single-source shortest paths

A
• 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
6
Q

How to construct D*?

A

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

7
Q

Key property of D*/dijktra’s algorithm

A

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}.

8
Q

What is the Floyd - Warshall algorithm?

A
9
Q

example algorithm execution

A

see slides