I've been spending time on Dijkstra variants lately, and ran into a constraint I hadn't seen handled on this platform: edges that are only usable during specific time windows. I contributed this problem and am sharing it here for discussion. I would appreciate any feedback or alternative solutions.
Problem Statement : Shortest Path with Time Windows | Dijkstra + 3D State
You are given a directed weighted graph of n nodes (0-indexed) and a list of edges where:
edges[i] = [u, v, w, open, close]
This represents a directed edge from u to v with travel cost w. However, each edge is only usable if your arrival time at node u falls within the window [open, close), i.e., open <= time < close.
Find the minimum cost to travel from node 0 to node n-1. If it is impossible, return -1.
Note: You may wait at a node for free. Waiting increases your arrival time by 1 per step. Cost of waiting = 0.
Examples
Example 1:
Input: n = 4, edges = [[0,1,2,0,5],[0,2,5,0,3],[1,3,3,2,10],[2,3,1,4,8]]
Output: 5
Explanation:
Path 0 -> 1 -> 3:
At node 0, t=0, edge [0,5) open. Cost=2. Arrive at node 1 at t=2.
At node 1, t=2, edge [2,10) open. Cost=3.
Total = 5. Alternative path 0->2->3 costs 6.Example 2:
Input: n = 3, edges = [[0,1,4,0,2],[1,2,3,5,9]]
Output: 7
Explanation:
Arrive at node 1 at t=4. Edge 1->2 opens at t=5.
Wait 1 step for free (t=5), then travel. Cost = 4+3 = 7.Example 3:
Input: n = 3, edges = [[0,1,5,0,10],[1,2,3,0,4]]
Output: -1
Explanation:
Arrive at node 1 at t=5. Edge 1->2 closes at t=4. Window shut. No path.Constraints
1 <= n <= 1000 <= edges.length <= 5001 <= w <= 10000 <= open < close <= 100- No self-loops
Why This Doesn't Reduce to Standard Dijkstra
In classic Dijkstra, state is just (cost, node). The first time you reach a node with the lowest cost, you're done with it; later arrivals at the same node can be discarded. That assumption breaks here, because the edges available to you depend on when you arrive, not just how much you've spent getting there.
Two paths reaching the same node with identical cost but different arrival times can have completely different futures: one might find every outgoing edge closed, while the other catches every window open. So the state has to expand to (cost, node, time), and a node can legitimately be visited multiple times at different timestamps.
Approach
- Push
(0, 0, 0)onto a min-heap ordered by cost — start at node 0, cost 0, time 0. - Pop the state with the smallest cost. If the node is
n-1, return that cost. - For each outgoing edge
(u->v, w, open, close): ifopen <= t < close, push(cost+w, v, t+w). - If any edge from this node opens later but not now, push
(cost, node, t+1)to simulate waiting one step for free. - Track
visited[node][time]so the same state is never expanded twice.
Time: O(E x T x log(E x T)), where T is the maximum close time (<= 100)
Space: O(N x T)
Solution (Java)
class Solution {
public int shortestPathTimeWindows(int n, int[][] edges) {
if (n == 1) return 0;
Map<Integer, List<int[]>> graph = new HashMap<>();
for (int i = 0; i < n; i++) graph.put(i, new ArrayList<>());
for (int[] e : edges)
graph.get(e[0]).add(new int[]{e[1], e[2], e[3], e[4]});
int MAX_TIME = 200;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.offer(new int[]{0, 0, 0});
boolean[][] visited = new boolean[n][MAX_TIME + 1];
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int cost = cur[0], node = cur[1], t = cur[2];
if (node == n - 1) return cost;
if (visited[node][t]) continue;
visited[node][t] = true;
boolean canWait = false;
for (int[] e : graph.get(node)) {
int nei = e[0], w = e[1], open = e[2], close = e[3];
if (open <= t && t < close) {
int nt = t + w;
if (nt <= MAX_TIME && !visited[nei][nt])
pq.offer(new int[]{cost + w, nei, nt});
}
if (close > t + 1) canWait = true;
}
if (canWait && t + 1 <= MAX_TIME && !visited[node][t + 1])
pq.offer(new int[]{cost, node, t + 1});
}
return -1;
}
}Dry Run (Example 1)
Input: n = 4, edges = [[0,1,2,0,5],[0,2,5,0,3],[1,3,3,2,10],[2,3,1,4,8]]
Heap starts with (cost=0, node=0, t=0)
Pop (0, 0, 0):
Node 0 is not the destination.
Edge 0->1: w=2, window [0,5). t=0 is inside the window. Push (2, 1, 2).
Edge 0->2: w=5, window [0,3). t=0 is inside the window. Push (5, 2, 5).
Mark (0,0) visited.
Pop (2, 1, 2) [smallest cost in heap]:
Node 1 is not the destination.
Edge 1->3: w=3, window [2,10). t=2 is inside the window. Push (5, 3, 5).
Mark (1,2) visited.
Pop (5, 2, 5) or (5, 3, 5) [tied on cost, order doesn't matter for correctness]:
If node 3 is popped first: node 3 == n-1 (4-1=3). Return cost = 5.
Result: 5, matching the expected output. The alternative path through node 2
(cost 5 to reach node 2, then cost 1 to reach node 3) would total 6, so it never
beats the path through node 1.Test Cases
n=4, edges=[[0,1,2,0,5],[0,2,5,0,3],[1,3,3,2,10],[2,3,1,4,8]] -> 5
n=3, edges=[[0,1,4,0,2],[1,2,3,5,9]] -> 7
n=3, edges=[[0,1,5,0,10],[1,2,3,0,4]] -> -1
n=4, edges=[[0,3,100,0,50],[0,1,1,0,50],[1,2,1,0,50],[2,3,1,0,50]] -> 3
n=1, edges=[] -> 0
n=2, edges=[[0,1,10,0,5],[0,1,3,0,5],[0,1,7,0,5]] -> 3Would love to hear thoughts — is this unique enough? Any edge cases I'm missing? Should this be Medium or Hard?
Tags: Graph, Dijkstra, Shortest Path, Priority Queue