12 Shortest Path

Question 1

Shortest Path Problem

Answer 1

Needs weighted graph that can be directed or undirected.

Weights can be:
1. Uniform
2. Non-Negative, Negative, Zero, or Positive.

Question 2

Single-source shortest paths problem:

Answer 2

Find a shortest path from a source (start) vertex ‘s’ to every other vertex ‘v’

Question 3

Single-pair shortest path problem:

Answer 3

Find a shortest path for a source (start) vertex ‘s’ to a goal vertex ‘g’.

Question 4

All pairs shortest-path problem:

Answer 4

Find a shortest path between all pairs of vertices.

Question 5

Breadth-First Search

Answer 5

Discovers all vertices at distance k from s before discovering any vertices at distance k+1.

Question 6

Total Running Time of BFS

Answer 6

O(V+E)

Question 7

If the graph is unweighted (or has uniform weights), the breadth-first tree is also:

Answer 7

A shortest path tree

Question 8

Dijkstra’s Algorithm

Answer 8

Solves the single-source shortest path problem in a weighted graph where all the weights are non-negative

Question 9

Total Time of Dijkstra’s Algorithm If Priority Queue is Vector

Answer 9

O(V^2 + E) = O(V^2)

Question 10

Total Time of Dijkstra’s Algorithm If Priority Queue is Binary Heap

Answer 10

O(V + E log V)

Connected Graph: O(E log V) since V = O(E)
Sparse graph: O(V log V) since E = O(V)

Question 11

Single Pair vs Single Source

Answer 11

Pair is solved more efficiently (on average) but its complexity analysis is somewhat different.