Cheapest Route Between Every Pair of Stations
Solve this ProblemA rail network has n stations and one-way links with positive prices, given as a price matrix. For every ordered pair of stations, find the cheapest total price of a route from the first to the second, or -1 if there is none.
Running a single-source algorithm from every station works, but the Floyd–Warshall algorithm computes the whole table with three nested loops by considering, one after another, each station as a possible middle stop.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ n ≤ 7 stations numbered 0 … n-1; roads is an n × n matrix: roads[u][v] = 0 (u ≠ v) means there is no one-way link from u to v, and roads[u][v] = w (1 ≤ w ≤ 20) means a link costing w - ◆
roads[u][u] = 0; all link prices are positive - ◆
The cheapest price from a station to itself is 0 - ◆
Return an n × n matrix whose entry [i][j] is the cheapest total price of a route from station i to station j, or -1 if station j cannot be reached from i
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Explore Every Route From Every Station
BruteFor each source station, explore every route that never visits a station twice, adding the prices, and keep the cheapest total found for each destination. With positive prices the cheapest route never repeats a station, so this is exact. It repeats the exponential search once per source station.
O(n · n!)O(n)1class Solution {
2 private void explore(int[][] roads, int u, int total, boolean[] onPath, int[] best) {
3 best[u] = Math.min(best[u], total);
4 onPath[u] = true;
5 for (int v = 0; v < roads.length; v++) {
6 if (roads[u][v] > 0 && !onPath[v]) {
7 explore(roads, v, total + roads[u][v], onPath, best);
8 }
9 }
10 onPath[u] = false;
11 }
12
13 public int[][] allPairs(int[][] roads) {
14 int n = roads.length;
15 int INF = Integer.MAX_VALUE;
16 int[][] result = new int[n][n];
17 for (int src = 0; src < n; src++) {
18 int[] best = new int[n];
19 Arrays.fill(best, INF);
20 explore(roads, src, 0, new boolean[n], best);
21 for (int j = 0; j < n; j++) {
22 result[src][j] = best[j] == INF ? -1 : best[j];
23 }
24 }
25 return result;
26 }
27}Optimal — Floyd–Warshall
OptimalKeep a table dist[i][j] of the cheapest known price from i to j: 0 on the diagonal, the link price where a link exists, and infinity elsewhere. Then allow the stations one by one as possible middle stops: for k = 0, 1, …, n − 1 and every pair (i, j), compare the current dist[i][j] with going through k, dist[i][k] + dist[k][j], and keep the smaller. After step k the table is exact for all routes whose middle stops are among 0 … k, so after the last step it is exact for all routes. Three nested loops: O(n³). Infinity entries are reported as -1.
O(n³)O(n²)1class Solution {
2 public int[][] allPairs(int[][] roads) {
3 int n = roads.length;
4 int INF = 1_000_000;
5 int[][] dist = new int[n][n];
6 for (int i = 0; i < n; i++) {
7 for (int j = 0; j < n; j++) {
8 if (i == j) dist[i][j] = 0;
9 else dist[i][j] = roads[i][j] > 0 ? roads[i][j] : INF;
10 }
11 }
12 for (int k = 0; k < n; k++) {
13 for (int i = 0; i < n; i++) {
14 for (int j = 0; j < n; j++) {
15 if (dist[i][k] + dist[k][j] < dist[i][j]) {
16 dist[i][j] = dist[i][k] + dist[k][j];
17 }
18 }
19 }
20 }
21 for (int i = 0; i < n; i++) {
22 for (int j = 0; j < n; j++) {
23 if (dist[i][j] >= INF) dist[i][j] = -1;
24 }
25 }
26 return dist;
27 }
28}