Comment on page
Cheapest Flights Within K Stops
Weighted Directed Graph
Medium
There are
ncities connected by mflights. Each fight starts from city uand arrives at vwith a pricew.Now given all the cities and flights, together with starting city
srcand the destination dst, your task is to find the cheapest price fromsrctodstwith up tokstops. If there is no such route, output-1.Example 1:
Input:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
Output:
200
Explanation:
The graph looks like this:
0
/ \
100 500
/ \
1 ---100--- 2
The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.
Example 2:
Input:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
Output:
500
Explanation:
The graph looks like this:
0
/ \
100 500
/ \
1 ---100--- 2
The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked red in the picture.
Note:
- The number of nodes
nwill be in range[1, 100], with nodes labeled from0ton - 1. - The size of
flightswill be in range[0, n * (n - 1) / 2]. - The format of each flight will be
(src, dst, price). - The price of each flight will be in the range
[1, 10000]. kis in the range of[0, n - 1].- There will not be any duplicated flights or self cycles.
Some explanation.
The key difference with the classic Dijkstra algo is, we don't maintain the global optimal distance to each node, i.e. ignore below optimization:
alt ← dist[u] + length(u, v)if alt < dist[v]:Because there could be routes which their length is shorter but pass more stops, and those routes don't necessarily constitute the best route in the end. To deal with this, rather than maintain the optimal routes with 0..K stops for each node, the solution simply put all possible routes into the priority queue, so that all of them has a chance to be processed. IMO, this is the most brilliant part.
And the solution simply returns the first qualified route, it's easy to prove this must be the best route.
Complexity Analysis
- Time Complexity: O(E+nlogn), where E is the total number of flights.?
- Space Complexity: O(n), the size of the heap.?
class Solution {
class Flight {
int src;
int dst;
int price;
Flight (int src, int dst, int price) {
this.src = src;
this.dst = dst;
this.price = price;
}
}
class Stop {
int id, cost, count;
Stop(int id, int cost, int count) {
this.id = id;
this.cost = cost;
this.count = count;
}
}
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
HashMap<Integer, ArrayList<Flight>> map = new HashMap<>();
for (int[] flight: flights) {
if (!map.containsKey(flight[0])) {
map.put(flight[0], new ArrayList<Flight>());
}
map.get(flight[0]).add(new Flight(flight[0], flight[1], flight[2]));
}
Comparator<Stop> cmp = new Comparator<Stop>() {
public int compare(Stop s1, Stop s2) {
return s1.cost - s2.cost;
}
};
PriorityQueue<Stop> q = new PriorityQueue<Stop>(cmp);
q.offer(new Stop(src, 0, K));
while (q != null && !q.isEmpty()) {
Stop cur = q.poll();
if (cur.id == dst) {
return cur.cost;
}
if (cur.count >= 0) {
List<Flight> list = map.get(cur.id);
if (list == null) {
continue;
}
for (Flight f: list) {
q.offer(new Stop(f.dst, f.price + cur.cost, cur.count - 1));
}
}
}
return -1;
}
}
k - number of flightsn - number of citiesTime Complexity:
O(n ^ (k + 1))Space Complexity:
O(k + 1)DFS中的剪枝很重要，否则会TLE
class Solution {
class Flight {
int src;
int dst;
int price;
Flight (int src, int dst, int price) {
this.src = src;
this.dst = dst;
this.price = price;
}
}
private static int cheapest;
private static boolean routeFound;
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
cheapest = Integer.MAX_VALUE;
routeFound = false;
HashMap<Integer, ArrayList<Flight>> map = new HashMap<>();
for (int[] flight: flights) {
if (!map.containsKey(flight[0])) {
map.put(flight[0], new ArrayList<Flight>());
}
map.get(flight[0]).add(new Flight(flight[0], flight[1], flight[2]));
}
boolean[] visited = new boolean[n];
dfs(map, visited, src, dst, 0, K);
if (!routeFound) {
return -1;
}
return cheapest;
}
private void dfs(HashMap<Integer, ArrayList<Flight>> map, boolean[] visited, int src, int dst, int cost, int k) {
if (src == dst) {
routeFound = true;
cheapest = Math.min(cheapest, cost);
return;
}
if (k < 0) {
return;
}
ArrayList<Flight> flights = map.get(src);
if (flights != null) {
for (Flight flight: flights) {
// do not visit same city twice
if (visited[flight.dst]) {
continue;
}
// Pruning: important to reduce computation
if (flight.price + cost > cheapest) {
continue;
}
visited[flight.dst] = true;
dfs(map, visited, flight.dst, dst, cost + flight.price, k - 1);
visited[flight.dst] = false;
}
}
}
}
// build map for adjacency list: (u -> (v1[w1], v2[w2]))
// u -> v : w
// DFS
// k : remaining stops
// src: current src
// dst: final dst
// if k < 0 return
// if src reach dst, update global min with current cost
// when all returned, return the global min
Last modified 3yr ago