Single Source Shortest Path

Question 1

What are 5 ways to solve the SSSP Problem?

Answer 1

1. BFS for Unweighted Graphs
2. O(VE) Bellman Ford’s Algorithm
3. One-pass Bellman Ford’s for DAG
4. Original Dijkstra’s Algorithm
5. Modified Dijkstra’s Algorithm

Question 2

What DS does SSSP problems use?

Answer 2

1. Array of size V for distances
2. Array of size V for predecessor

Question 3

How does the initialisation step work?

Answer 3

For all vertices, the distance is set to be infinity other than the source which is 0. Predecessors of every vertex is -1.

Question 4

How does the relaxation operation work?

Answer 4

For vertices a and b we check if the current cost of travelling to b is greater than the cost of travelling to a + cost of travelling from a to b using the current edge.

Question 5

How does BFS for unweighted graphs work?

Answer 5

1. Run BFS from source vertex s
2. If we want the shortest path to v, we reconstruct the path using the resultant predecessor array starting from index v

We can change the visited array to a distance array as well. Change the updating of the visited array to the updating of the shortest distance.

Question 6

Time Complexity of BFS

Answer 6

O(V + E)

Question 7

How does Bellman Ford work?

Answer 7

Relax all E edges V-1 times, without a need for any order of relaxation. After V-1 relaxations of every edge, if there are no negative weight cycles, SSSP problem is solved. Thus, we can even use this algorithm to detect for negative weight cycles and terminate if so to prevent infinite loop.

Question 8

Time Complexity of Bellman Ford

Answer 8

O(VE)

Question 9

Why does BFS / DFS work for trees?

Answer 9

In a tree, every path between any two vertices is the shortest path, as there is only one unique path between any 2 vertices. Trees tend to be undirected, and even if there is a negative weight cycle, it tends to be trivial (looping between 2 adjacent vertices).

Question 10

Time Complexity of BFS / DFS for trees

Answer 10

O(V) since O(V + V - 1)

Question 11

How does One-pass Bellman Ford for DAG work?

Answer 11

1. Topologically sort the vertices using Kahn’s Algorithm or DFS
2. Run Bellman Ford across all edges once in topological order.

Question 12

Time complexity of One-pass Bellman Ford for DAG

Answer 12

O(V + E) -> Topological sort - O(V + E), Iterating through - O(V + E)

Question 13

How does Original Dijkstra’s Algorithm for graph with no negative edge weight work?

Answer 13

1. Look at all current path estimates and the “receiving vertex”. Pick the one with minimum value. At the start, it will only be the source, which has estimate 0.
2. We relax the edges going out of the receiving vertex, updating the existing path estimates.
3. Once the receiving vertex has been chosen, we add to set of solved vertices, which is a set of vertices whose final shortest path weights have been determined.

Question 14

What DS does Dijkstra’s use?

Answer 14

Priority Queue for shortest path estimate. Array for distance array and predecessor array. Hash table to find vertices quickly.

Question 15

How does Original Dijkstra’s work with respect to its DS?

Answer 15

1. Store the shortest path estimate for vertex v as an Integer Pair (d,v) in the Priority Queue, where d = D[v]
2. Enqueue (inf, v) for all vertices except for source s, (0, s)
3. Remove vertex u with minimum d from PQ. Add u to set of Solved vertices. Relax all its outgoing edges.
4. If edge (u, v) was relaxed, find v quickly using the hash table.

Question 16

T or F: If G = (V, E) contains no negative weight cycle, then the shortest path p from s to v is a simple path.

Answer 16

True

Question 17

T or F: If G = (V, E) contains no negative weight cycle, then after Bellman Ford’s terminates D[v] = delta(s, v) for all v

Answer 17

True

Define vi to be any vertex that has shortest path p taking i number of edges from s. After i passes through E, we have D[vi] = delta(s, vi). Thus, after V-1 iterations, the furthest vertex Vv-1 from s has the shortest path from s.

Question 18

T or F: Subpaths of a shortest path are shortest paths

Answer 18

True

Question 19

T or F: For Dijkstra’s, after vertex v is added to Solved, shortest path from s to v has been found.

Answer 19

True.

The later vertices have their shortest paths built from the shortest paths of already solved vertices.

Question 20

Time Complexity of Original Dijkstra’s

Answer 20

O((V+E)logV)

PriorityQueueing: Each vertex will only be queued and dequeued once. This will happen O(V) times. Each queue and dequeue will take O(logV) if we use bBST. -> O(VlogV)

Relaxation: All E edges are processed only once. Update of shortest path estimate takes O(logV) time. -> O(ElogV)

Overall: O((V + E)logV)

Question 21

How does Modified Dijkstra’s work for graphs with no negative weight cycles?

Answer 21

Useful when there are negative weight edges, but no negative weight cycles.

1. Extract pair (d,u) in front of the PQ with the minimum shortest path estimate so far.
2. If d = D[u], we relax all edges out of u.
3. if d > D[u], we discard this inferior (d,u) pair.
4. If during edge relaxation, D[v] of a neighbour v of u decreases, enqueue a new (D[v], v) pair for future propagation of shortest path estimate.