Variations of Shortest Path: From LeetCode 787 - Wed, Sep 18, 2024

Dijkstra’s Algorithm

Dijkstra’s algorithm is a dynamic programming algorithm that exploits the fact that in a graph with non-negative weights, the shortest path from a source to a destination has an optimal substructure. The algorithm maintains a priority queue to explore the nearest unvisited node and updates the distances to its neighbors.

More specifically, the algorithm splits all vertices into two sets: the set of vertices whose shortest distance from the source is known \(S\) and the set of vertices whose shortest distance is unknown (\(T\)). It repeatedly selects the vertex with the smallest known distance, adds it to the known set, and updates the distances to its neighbors.

The first step is to initialize the shortest distance \(dis[v]\) such that \(dis[src] = 0\) and \(dis[v] = \infty\) for all other vertices \(v\).

At each iteration, we do the following until we have processed all vertices (\(|T| = \{\}\)):

1. Find the vertex \(u\) in \(T\) with the smallest distance \(dis[u]\).
2. Add \(u\) to \(S\).
3. Perform relaxation for all neighbors \(v\) of \(u\): if \(dis[v] > dis[u] + w(u, v)\), then update \(dis[v] = dis[u] + w(u, v)\).

Bellman-Ford Algorithm

Compared to Dijkstra’s algorithm, we are not doing dynamic programming here (note the absence of the priority queue). Instead, every edge is relaxed in one iteration. This will be repeated for a total of \(|V| - 1\) iterations, where \(|V|\) is the number of vertices in the graph.

Approach 1: Modified Bellman-Ford

It is straightforward to think that we can directly use the Bellman-Ford algorithm to solve this problem. However, the challenge is to incorporate the constraint on the number of stops.

Recall that the Bellman-Ford will relax all edges for \(|V| - 1\) iterations. To incorporate the constraint on the number of stops, we can modify the algorithm to only relax edges for \(k + 1\) iterations (since we can have at most \(k\) stops, we need to consider \(k + 1\) edges).

Here is the modified Bellman-Ford algorithm:

1. Initialize a distance array dis of size n with float('inf'), and set dis[src] = 0.
2. For i from 0 to k:
   • Create a copy of the current distance array temp_dis.
   • For each edge (u, v, price) in flights:
     • If dis[u] != float('inf') and dis[u] + price < temp_dis[v], then update temp_dis[v] = dis[u] + price.
   • Update dis with temp_dis.
3. Return dis[dst] if it is not float('inf'), otherwise return -1.

The caveat here is the copy. Why do we need to create a copy of the distance array? This is to ensure that we are only considering the distances from the previous iteration when relaxing edges. While this does not matter in the standard Bellman-Ford algorithm, it is crucial here because we are limiting the path length. Updating the distance array in place would violate the invariant that a shortest path is only relaxed at most once per iteration.

Approach 2: BFS with Priority Queue

On the LeetCode official solution, this is called a modified Dijkstra’s algorithm. However it is more akin to a BFS with a priority queue. The idea is to use a priority queue to explore the graph while keeping track of the number of stops.

The invariant here is that instead of a visited set, we maintain the number of steps when the node is last visited. A node is only explored if the current number of stops is less than the previous recorded number of stops, or if it has not been visited before.

This is really just BFS with a PQ, where we explore the cheapest path first. And the existence of this PQ is totally unnecessary, since regular BFS works just fine. PQ insertion added complexity without any real benefit.