Cheapest Routes Through a One-Way Freight Network
Solve this ProblemA freight company has n depots connected by one-way routes that never form a cycle. The routes are given as a cost matrix: cost[u][v] is the price of the route from u to v, or 0 if there is no such route. Goods start at the source depot. For every depot, find the cheapest total cost of getting goods there, or -1 if it cannot be reached.
Because there are no cycles, the depots can be processed in topological order and each depot's cost is final when its turn comes.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ n ≤ 10 depots numbered 0 … n-1; cost is an n × n matrix: cost[u][v] = 0 means there is no route from u to v, and cost[u][v] = w (1 ≤ w ≤ 20) means a one-way route u → v costing w - ◆
The routes contain no cycle (the network is a directed acyclic graph); cost[u][u] = 0 - ◆
0 ≤ src < n is the depot where the goods start - ◆
Return an array where entry i is the cheapest total cost from src to depot i, or -1 if depot i cannot be reached
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Keep Relaxing Costs Until Nothing Improves
BruteGive the source cost 0 and every other depot infinity. Sweep over all pairs (u, v) again and again: if depot u has a known cost and there is a route u → v, then reaching v through u costs cost[u] + cost[u][v]; keep it when it is cheaper. Stop when a whole sweep changes nothing (at most n sweeps of n² pairs), then turn infinities into -1. O(n³) with a cost matrix.
O(n³)O(n)1class Solution {
2 public int[] cheapestFromSource(int[][] cost, int src) {
3 int n = cost.length;
4 int INF = Integer.MAX_VALUE;
5 int[] dist = new int[n];
6 Arrays.fill(dist, INF);
7 dist[src] = 0;
8 boolean changed = true;
9 while (changed) {
10 changed = false;
11 for (int u = 0; u < n; u++) {
12 if (dist[u] == INF) continue;
13 for (int v = 0; v < n; v++) {
14 if (cost[u][v] > 0 && dist[u] + cost[u][v] < dist[v]) {
15 dist[v] = dist[u] + cost[u][v];
16 changed = true;
17 }
18 }
19 }
20 }
21 for (int i = 0; i < n; i++) {
22 if (dist[i] == INF) dist[i] = -1;
23 }
24 return dist;
25 }
26}Optimal — Relax the Routes in Topological Order
OptimalIn a graph without cycles, the depots can be lined up so that every route goes from earlier to later depots (a topological order, found here with Kahn's algorithm). If we relax the outgoing routes of the depots in that order, then when a depot's turn comes, all routes that can reach it have already been relaxed, so its cost is final. So one pass suffices: no repeated sweeps. Depots that cannot be reached from the source keep infinity and become -1.
O(n²) with a matrix (O(n + E) with lists)O(n)1class Solution {
2 public int[] cheapestFromSource(int[][] cost, int src) {
3 int n = cost.length;
4 int INF = Integer.MAX_VALUE;
5 int[] indegree = new int[n];
6 for (int u = 0; u < n; u++) {
7 for (int v = 0; v < n; v++) {
8 if (cost[u][v] > 0) indegree[v]++;
9 }
10 }
11 int[] dist = new int[n];
12 Arrays.fill(dist, INF);
13 dist[src] = 0;
14 Deque<Integer> queue = new ArrayDeque<>();
15 for (int i = 0; i < n; i++) {
16 if (indegree[i] == 0) queue.add(i);
17 }
18 while (!queue.isEmpty()) {
19 int u = queue.poll();
20 for (int v = 0; v < n; v++) {
21 if (cost[u][v] == 0) continue;
22 if (dist[u] != INF && dist[u] + cost[u][v] < dist[v]) {
23 dist[v] = dist[u] + cost[u][v];
24 }
25 indegree[v]--;
26 if (indegree[v] == 0) queue.add(v);
27 }
28 }
29 for (int i = 0; i < n; i++) {
30 if (dist[i] == INF) dist[i] = -1;
31 }
32 return dist;
33 }
34}