Time complexity of using BFS to find shortest path within k stops

Question

I'm referencing this Leetcode question: https://leetcode.com/problems/cheapest-flights-within-k-stops/solution/, which asks you to find the length of the shortest path from source to dest using less than or equal to K intermediate nodes.

Since the solution is behind a paywall, I've taken screenshots of the solution and copy/pasted the solution code. Here it is (fyi, "price" and "distance" are synonymous -- they just mean the weights of the graph):

Approach 1: Breadth First Search

Intuition:

A breadth-first search is a good algorithm to use if we want to find the shortest path in an unweighted graph. The property of BFS is that the first time a node is reached during the traversal, it is reached at the minimum distance from the source. The same cannot be said for a weighted graph. For a weighted graph, a path having more edges does not necessarily mean the path is more expensive. Thus, we cannot employ a normal breadth-first search for weighted graphs.

A breadth-first search has no way of knowing if a particular discovery of a node would give us the cheapest path to that node. The only possible way for BFS (or DFS) to find the shortest path in a weighted graph is to search the entire graph and keep recording the minimum distance from the source to the destination node.

However, our problem limits the number of stops to $k$. As a result, we need not search the paths with lengths greater than $k + 1$. A breadth-first search can be used for this problem because the number of levels to be explored by the algorithm is bounded by $k$.

In this approach, we will perform a level-wise iteration over the nodes. We will explore all the nodes at the present level (say $l$) before moving on to the nodes at the next level ($l + 1$). This level would correspond to the number of stops that would be limited by $k$. When we move from a level of $l$ to $l + 1$, we will increase the stops by 1. We are allowed a maximum of $k$ stops, which means we could go up to a maximum level of $k + 1$ from the src node, trying to reach dst at the minimum price.

We can maintain an array dist which stores the minimum price to reach each node. When we want to move to a node, we will only consider edges where the total price after traversing the edge is less than the currently calculated dist[node]. This optimization helps us avoid TLE.

Algorithm:

1. Create an adjacency list where adj[X] contains all the neighbors of node X and the corresponding price it takes to move to a neighbor.
2. Intialize dist array, storing the minimum price to reach a node from the src node. Intialize it with large values.
3. Initialize a queue storing {node, distance} pairs. Initially, the queue should have only {src, 0}.
4. Create a variable called stops and set its value to 0.
5. Perform BFS until the queue is empty or stops > k:
   • Iterate over all the nodes at a particular level. This will be done by starting a nested loop and visiting all the nodes currently present in the queue.
   • At each pair {node, distance}, iterate over all the neighbors of node. For each neighbour, check if dist[neighbor] is less than distance + the price of the edge. If it is, then update dist[neighbor] and push {neighbor, dist[neighbor]} onto the queue.
   • After iterating over all the nodes in the current level, increase stops by one. We've visited all the nodes at a particular level and are ready to visit the next level of nodes.
6. Once we reach a condition where either the queue is empty or stops == k, we have our answer as dist[dst]. If dist[dst] hasn't changed from the initial large value, then we never reached it, so return -1.

Solution code (in Java):

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        Map<Integer, List<int[]>> adj = new HashMap<>();
        for (int[] i : flights)
            adj.computeIfAbsent(i[0], value -> new ArrayList<>()).add(new int[] { i[1], i[2] });

        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);

        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] { src, 0 });
        int stops = 0;

        while (stops <= k && !q.isEmpty()) {
            int sz = q.size();
            // Iterate on current level.
            while (sz-- > 0) {
                int[] temp = q.poll();
                int node = temp[0];
                int distance = temp[1];

                if (!adj.containsKey(node))
                    continue;
                // Loop over neighbors of popped node.
                for (int[] e : adj.get(node)) {
                    int neighbour = e[0];
                    int price = e[1];
                    if (price + distance >= dist[neighbour])
                        continue;
                    dist[neighbour] = price + distance;
                    q.offer(new int[] { neighbour, dist[neighbour] });
                }
            }
            stops++;
        }
        return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
    }
}

Complexity Analysis:

Let $E$ be the number of flights and $N$ be the number of cities.

Time complexity: $O(N + E \cdot K)$. Depending on improvements in the shortest distance for each node, we may process each edge multiple times. However, the maximum number of times an edge can be processed is limited by $K$ because that is the number of levels we will investigate in this algorithm. In the worst case, this takes $O(E \cdot K)$ time. We also need $O(E)$ to initialize the adjacency list and $O(N)$ to initialize the dist array.

Space Complexity: $O(N + E \cdot K)$. We are processing at most $E \cdot K$ edges, so the queue takes up $O(E \cdot K)$ space in the worst case. We also need $O(E)$ space for the adjacency list and $O(N)$ space for the dist array.

The worst case time complexity of Leetcode BFS solution is stated as $O(N + E \cdot K)$. However, I'm confused why it isn't a factorial time complexity.

Imagine a strongly-connected directed graph with 4 nodes (numbered 1 to 4) and $K = 2$. If you draw a BFS tree with the following levels:

Level 1: Node 1 (the source node)

Level 2: Nodes 2, 3, 4

Level 3: Nodes 3, 4 (under Node 2 from previous level); Nodes 2, 4 (under Node 3 from previous level); Nodes 2, 3 (under Node 4 from previous level)

... (you can fill in level 4)

Then its clear the number of nodes in this tree is $O((N-1) \cdot (N-2)...(N-K-1))$. That is a factorial complexity. Why is the actual worst case time complexity written in the solution $O(N + E \cdot K)$ instead?

Answer 1

Too long; did not read.

The easy solution: Let $w' = w + 10^{12}$. Now, find a solution of cost less than $k \cdot 10^{12}$

---

The more involved solution, but which in fact solves a more general problem:

From an input instance $G, s, t$ (assuming here the graph is directed, but it doesn't really matter).

Create $k$ copies $G_1, G_2, ..., G_k$ of the original graph.

However, for every vertex $v_i^j$ in $G_i$, make the edges out of $v_i^j$ point to its neighbors in $G_{i+1}$ instead.

And then, create a new $t'$ such that every copy of $t$, $t_1, t_2, ..., t_k$ points to $t'$, and then run BFS from $s$ to $t'$ in $G' = \bigcup {G_1, ..., G_k}$.

Now, $G'$ has at most $kn + 1$ vertices and $m + k$ edges.

---

Ps, the reason I say it solves a more general problem, is that you can use this technique to solve the version where you are allowed to use at most $k$ of a specific set $U \subseteq V$ of the vertices. In this case, whenever you use a vertex from $U$, you transport to the next layer, otherwise you are allowed to remain in the same layer.

Answer 2

Reminder ; when doing a BFS, you are keeping track of vertices you already visited. If you see a node that you already visited, you do not consider it and you "stop" there. This explains how the algorithm is not $N!$. Now as for the complexity given by the website, considering that BFS is $O(|V| + |E|)$, an "easier" version of it (the algorithm is just a BFS with an early stop) will clearly not be $O(|V| + k \cdot |E|)$, because $$ O(|V| + |E|) \subset O(|V| + k \cdot |E|)$$ for $k \geq 1$