Code Logo

Shuttle Time with Dijkstra

Published at22 Apr 2026
Created by
Dijkstra Easy 0 views
Like0

A campus shuttle system connects stops with travel times. You are given the number of stops, a list of two-way routes in the form [u, v, time], and two stops called start and destination.

Your task is to return the minimum total travel time needed to go from the start stop to the destination stop. Some routes may look shorter because they use fewer hops, but they can still cost more time overall. What matters is the total sum of travel times along the route you choose.

For example, if one path takes times 4 + 3 and another path takes 2 + 6 + 1, the answer should come from whichever total is smaller.

If the destination cannot be reached from the start at all, return -1. This challenge is a simple introduction to using Dijkstra's algorithm on a weighted graph.

Example Input & Output

Example 1
Input
n = 1, roads = [], start = 0, destination = 0
Output
0
Explanation

Starting and ending at the same stop costs zero travel time.

Example 2
Input
n = 5, roads = [[0,1,4], [1,2,3], [0,3,2], [3,4,6], [4,2,1]], start = 0, destination = 2
Output
7
Explanation

The fastest route is 0 -> 1 -> 2 with total time 7.

Example 3
Input
n = 3, roads = [[0,1,7]], start = 0, destination = 2
Output
-1
Explanation

Stop 2 is disconnected, so the destination cannot be reached.

Algorithm Flow

Recommendation Algorithm Flow for Shuttle Time with Dijkstra
Recommendation Algorithm Flow for Shuttle Time with Dijkstra

Solution Approach

This problem is a classic shortest-path task on a weighted graph, which makes Dijkstra's algorithm the natural solution.

First build an adjacency list so each stop can quickly tell you which neighboring stops it connects to and how much each move costs. Then create a distance array where dist[x] stores the best travel time found so far for stop x.

Start from start with distance 0 and place that pair into a min-priority queue. Each time you remove the stop with the smallest current distance, try relaxing all outgoing routes. If going through that stop gives a neighbor a smaller total time, update the distance and push the new pair into the queue.

A compact Java structure looks like this:

PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.offer(new int[]{0, start});

When the destination is removed from the queue, that travel time is already the minimum possible. If the queue empties without reaching it, then no valid path exists and the answer is -1.

The runtime is O((n + m) log n) for m routes, and the extra space is mainly the adjacency list, distance array, and priority queue.

Best Answers

java
import java.util.*;

class Solution {
    public int shuttle_time_with_dijkstra(int n, int[][] roads, int start, int destination) {
        List<int[]>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] road : roads) {
            graph[road[0]].add(new int[]{road[1], road[2]});
            graph[road[1]].add(new int[]{road[0], road[2]});
        }

        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, start});

        while (!pq.isEmpty()) {
            int[] state = pq.poll();
            int cost = state[0];
            int node = state[1];
            if (cost != dist[node]) {
                continue;
            }
            if (node == destination) {
                return cost;
            }
            for (int[] edge : graph[node]) {
                int next = edge[0];
                int candidate = cost + edge[1];
                if (candidate < dist[next]) {
                    dist[next] = candidate;
                    pq.offer(new int[]{candidate, next});
                }
            }
        }
        return -1;
    }
}