What are 5 ways to solve the SSSP Problem?
- BFS for Unweighted Graphs
- O(VE) Bellman Ford’s Algorithm
- One-pass Bellman Ford’s for DAG
- Original Dijkstra’s Algorithm
- Modified Dijkstra’s Algorithm
What DS does SSSP problems use?
- Array of size V for distances
- Array of size V for predecessor
How does the initialisation step work?
For all vertices, the distance is set to be infinity other than the source which is 0. Predecessors of every vertex is -1.
How does the relaxation operation work?
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.
How does BFS for unweighted graphs work?
- Run BFS from source vertex s
- 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.
Time Complexity of BFS
O(V + E)
How does Bellman Ford work?
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.
Time Complexity of Bellman Ford
O(VE)
Why does BFS / DFS work for trees?
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).
Time Complexity of BFS / DFS for trees
O(V) since O(V + V - 1)
How does One-pass Bellman Ford for DAG work?
- Topologically sort the vertices using Kahn’s Algorithm or DFS
- Run Bellman Ford across all edges once in topological order.
Time complexity of One-pass Bellman Ford for DAG
O(V + E) -> Topological sort - O(V + E), Iterating through - O(V + E)
How does Original Dijkstra’s Algorithm for graph with no negative edge weight work?
- 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.
- We relax the edges going out of the receiving vertex, updating the existing path estimates.
- 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.
What DS does Dijkstra’s use?
Priority Queue for shortest path estimate. Array for distance array and predecessor array. Hash table to find vertices quickly.
How does Original Dijkstra’s work with respect to its DS?
- Store the shortest path estimate for vertex v as an Integer Pair (d,v) in the Priority Queue, where d = D[v]
- Enqueue (inf, v) for all vertices except for source s, (0, s)
- Remove vertex u with minimum d from PQ. Add u to set of Solved vertices. Relax all its outgoing edges.
- If edge (u, v) was relaxed, find v quickly using the hash table.
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.
True
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
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.
T or F: Subpaths of a shortest path are shortest paths
True
T or F: For Dijkstra’s, after vertex v is added to Solved, shortest path from s to v has been found.
True.
The later vertices have their shortest paths built from the shortest paths of already solved vertices.
Time Complexity of Original Dijkstra’s
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)
How does Modified Dijkstra’s work for graphs with no negative weight cycles?
Useful when there are negative weight edges, but no negative weight cycles.
- Extract pair (d,u) in front of the PQ with the minimum shortest path estimate so far.
- If d = D[u], we relax all edges out of u.
- if d > D[u], we discard this inferior (d,u) pair.
- 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.
