What is the Single-Source Shortest Path Problem?
Learn single-source shortest path, when to use BFS, Dijkstra, or Bellman-Ford, and how to answer this graph algorithms interview question.
Expected Interview Answer
Single-source shortest path (SSSP) finds the minimum-cost route from one fixed source vertex to every other reachable vertex in a graph, solved with BFS for unweighted graphs, Dijkstra's algorithm for non-negative weights, and Bellman-Ford when negative edge weights are possible.
The algorithm choice depends entirely on edge weights. BFS explores level by level using a plain queue and works only when every edge costs the same, since it implicitly counts hops. Dijkstra's algorithm greedily relaxes the cheapest known frontier vertex first using a min-heap, achieving O((V + E) log V) time, but it breaks silently on negative weights because it never revisits a vertex once finalized. Bellman-Ford relaxes every edge V-1 times, tolerating negative weights and even detecting negative cycles, at the cost of slower O(V * E) time. All three maintain a distance array initialized to infinity except the source, and a predecessor array to reconstruct the actual path afterward.
- Finds optimal-cost paths, not just any path
- Distance array doubles as a reachability check
- Predecessor array reconstructs the full route
- Dijkstra scales well on sparse, non-negative graphs
AI Mentor Explanation
Single-source shortest path is like a fielding coach figuring out the fastest relay-throw route from the boundary rope back to the keeper through any combination of infielders. Each possible throw between two fielders has a time cost, and the coach keeps a running best-time table, updating it the moment a shorter relay through a particular fielder is found. Unweighted throws (assume every throw takes one second) reduce this to a simple queue-based sweep outward from the boundary. But real throws vary in speed, so the coach always picks the fielder with the current cheapest confirmed time next, exactly like Dijkstra selecting the nearest unfinalized vertex.
Step-by-Step Explanation
Step 1
Initialize distances
Set source distance to 0 and every other vertex to infinity; keep a predecessor map for path reconstruction.
Step 2
Pick the right algorithm for the weights
Unweighted → BFS; non-negative weights → Dijkstra with a min-heap; possible negative weights → Bellman-Ford.
Step 3
Relax edges repeatedly
For each edge (u, v, w), if dist[u] + w < dist[v], update dist[v] and set predecessor[v] = u.
Step 4
Reconstruct the path
Walk backward from the target through predecessor pointers to the source to recover the actual shortest route.
What Interviewer Expects
- Name the right algorithm per weight scenario (BFS, Dijkstra, Bellman-Ford)
- Explain the relaxation step precisely
- State Dijkstra fails with negative weights and why
- Give the correct time complexities for each algorithm
Common Mistakes
- Using Dijkstra on a graph with negative edge weights
- Forgetting to track predecessors, making path reconstruction impossible
- Confusing single-source shortest path with all-pairs shortest path
- Not distinguishing BFS (unweighted) from Dijkstra (weighted) use cases
Best Answer (HR Friendly)
“Single-source shortest path answers: starting from one specific point, what is the cheapest way to reach every other point in the network? I pick the algorithm based on the weights involved — a simple queue if all steps cost the same, Dijkstra's algorithm if costs vary but are never negative, and Bellman-Ford if negative costs are possible.”
Code Example
import heapq
def dijkstra(graph, source):
dist = {source: 0}
prev = {}
visited = set()
heap = [(0, source)]
while heap:
d, u = heapq.heappop(heap)
if u in visited:
continue
visited.add(u)
for v, weight in graph.get(u, []):
new_dist = d + weight
if new_dist < dist.get(v, float("inf")):
dist[v] = new_dist
prev[v] = u
heapq.heappush(heap, (new_dist, v))
return dist, prev
def reconstruct_path(prev, source, target):
path = [target]
while path[-1] != source:
path.append(prev[path[-1]])
return path[::-1]Follow-up Questions
- Why does Dijkstra's algorithm fail on negative edge weights?
- How does Bellman-Ford detect a negative cycle?
- How would you adapt Dijkstra to also count the number of shortest paths?
- What is the time complexity difference between array-based and heap-based Dijkstra?
MCQ Practice
1. Which algorithm correctly finds single-source shortest paths in a graph with negative edge weights but no negative cycle?
Bellman-Ford relaxes all edges V-1 times and correctly handles negative weights, unlike Dijkstra.
2. What is the time complexity of Dijkstra's algorithm using a binary min-heap?
Each vertex is popped once and each edge can trigger a heap push, giving O((V + E) log V).
3. For an unweighted graph, which algorithm finds single-source shortest paths most efficiently?
BFS explores level by level, and since every edge has equal cost, the level number is exactly the shortest distance.
Flash Cards
What does SSSP compute? — The minimum-cost path from one fixed source vertex to every other reachable vertex.
Which algorithm handles negative edge weights? — Bellman-Ford; Dijkstra assumes non-negative weights.
What is the relaxation condition? — If dist[u] + weight(u, v) < dist[v], update dist[v] and set predecessor[v] = u.
What is used to reconstruct the shortest path after computing distances? — A predecessor array, walked backward from target to source.