Campus Shuttle Path with Dijkstra
A shuttle coordinator has a weighted map of campus roads and wants to show the exact stop sequence for the best route between two places. Each road is two-way and written as [u, v, cost].
You are given the number of stops, the road list, a start stop, and a destination stop. Return the actual shortest path as an array of stop numbers in travel order. If the destination cannot be reached, return an empty array.
This challenge is still based on Dijkstra's algorithm, but the required output is different from the usual version. Knowing the minimum cost alone is not enough. The shuttle coordinator needs the sequence of stops that makes up that cheapest route so it can be displayed directly on a planning board.
That means the algorithm has to remember how each stop was reached when a better distance is found. Later, after the distances are finished, the path can be rebuilt by walking backward from the destination through those recorded parent links.
This makes the problem a good medium-level exercise. The shortest-path search itself is standard, but the reconstruction step adds a second layer of reasoning and bookkeeping that users need to understand clearly.
Example Input & Output
If the start and destination are the same, the path contains that one stop.
Stop 3 is unreachable, so the returned path is empty.
The minimum-cost route goes through stop 1, so the path is [0, 1, 4].
Algorithm Flow
Solution Approach
Dijkstra's algorithm still handles the distance calculation. The extra work is to store enough information so the path can be rebuilt at the end.
In addition to the distance array, keep a parent array where parent[x] records which previous node led to the current best distance for node x. Whenever a better route to next is discovered, update both dist[next] and parent[next].
That update step usually looks like this:
After the priority queue finishes, check whether the destination was reached. If not, return an empty array. If it was reached, rebuild the answer by starting from the destination and repeatedly following the parent links backward until the start is reached. Because that reconstruction goes backward, you can collect the nodes in a list and reverse it at the end, or insert each node at the front.
This pattern is common in real pathfinding tasks. Often the shortest distance is not enough by itself; the user also needs the actual route. Dijkstra plus parent tracking is the standard way to provide both pieces of information.
The runtime remains O((n + m) log n), and the parent array adds only O(n) extra space beyond the normal shortest-path structures.
Best Answers
import java.util.*;
class Solution {
public int[] campus_shuttle_path_with_dijkstra(int n, int[][] roads, int start, int destination) {
List<List<int[]>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] road : roads) {
graph.get(road[0]).add(new int[]{road[1], road[2]});
graph.get(road[1]).add(new int[]{road[0], road[2]});
}
int[] dist = new int[n];
int[] parent = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
Arrays.fill(parent, -1);
dist[start] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
pq.offer(new int[]{0, start});
while (!pq.isEmpty()) {
int[] current = pq.poll();
int cost = current[0];
int node = current[1];
if (cost > dist[node]) {
continue;
}
for (int[] edge : graph.get(node)) {
int next = edge[0];
int candidate = cost + edge[1];
if (candidate < dist[next]) {
dist[next] = candidate;
parent[next] = node;
pq.offer(new int[]{candidate, next});
}
}
}
if (dist[destination] == Integer.MAX_VALUE) {
return new int[0];
}
List<Integer> path = new ArrayList<>();
for (int node = destination; node != -1; node = parent[node]) {
path.add(node);
}
Collections.reverse(path);
int[] result = new int[path.size()];
for (int i = 0; i < path.size(); i++) {
result[i] = path.get(i);
}
return result;
}
}Comments (0)
Join the Discussion
Share your thoughts, ask questions, or help others with this Challenge.