Cheapest Flights Within K Stops

Weighted Directed Graph

Medium

There arencities connected by mflights. Each fight starts from city uand arrives at vwith a pricew.

Now given all the cities and flights, together with starting citysrcand 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 flights will 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].
k is in the range of [0, n - 1].
There will not be any duplicated flights or self cycles.

Solution

Dijkstra's Algorithm (BFS) with PriorityQueue Implementation

Inspired by: https://leetcode.com/problems/cheapest-flights-within-k-stops/discuss/115541/JavaPython-Priority-Queue-Solution

@bwv988: https://leetcode.com/problems/cheapest-flights-within-k-stops/discuss/115541/JavaPython-Priority-Queue-Solution/222415

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;
    }

}

DFS with Pruning

k - number of flights

n - number of cities

Time 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

Reference

https://leetcode.com/problems/cheapest-flights-within-k-stops/solution/

PreviousFlood Fill NextEvaluate Division

Last updated 4 years ago