Shortest Distance After Road Addition Queries I - Video Solutions

Problem Overview: You start with n cities connected in a straight line where each city i has a road to i+1. Queries add new directed roads between cities. After each addition, compute the shortest distance from city 0 to city n-1.

Approach 1: Breadth-First Search (BFS) Recompute per Query (Time: O(q*(n+e)), Space: O(n+e))

Maintain an adjacency list representing the current graph. Initially add edges i → i+1 for all cities. For every query (u, v), append the new edge to the adjacency list and run a Breadth-First Search starting from node 0. Since all roads have equal weight, BFS naturally finds the shortest number of edges to each city. The first time you reach n-1 gives the shortest path length. This approach is straightforward and works well because constraints keep the graph relatively small. Each query triggers a fresh traversal of the graph.

Approach 2: Dijkstra with Priority Queue (Time: O(q*(n+e) log n), Space: O(n+e))

Another option is running Dijkstra's Algorithm after each road insertion. Store the graph in an adjacency list and use a min-heap to always expand the node with the smallest current distance. Although all edges have weight 1 (making BFS slightly more efficient), Dijkstra provides a general solution for shortest paths and works even if weights change in future variations. After each query, push the start node 0 into the priority queue and relax edges until reaching n-1. The priority queue ensures nodes are processed in increasing distance order.

Recommended for interviews: BFS is typically expected because every road has equal weight. Running BFS after each query demonstrates understanding of shortest paths in unweighted graphs and keeps implementation simple. Mentioning the Dijkstra alternative shows awareness of weighted graph techniques and broader problem-solving skills.