Dijkstra Algorithm with Restrictions
Prerequisite
Before reading this article, you need to learn:
In the previous article Core Principles and Implementation of Dijkstra Algorithm, we derived the Dijkstra algorithm from the standard BFS algorithm to solve the standard shortest path problem in weighted graphs.
In this article, we will talk about a more complex situation: the shortest path problem with restrictions.
This kind of problem is more complex than the standard shortest path problem. But don't worry, you only need to slightly change the Dijkstra template from the previous article to solve it. So, make sure you have fully understood the previous chapter.
Shortest Path Problem with Restrictions
In the last chapter, we used the third version of the three BFS traversal methods for the Dijkstra algorithm. Each node kept its own State object, so it is easy to extend the standard Dijkstra algorithm to solve more complex tasks.
For example, now you need to find the shortest path, but the path can have at most k edges.
You can still use the Dijkstra algorithm for this case, but you need to change the enqueue and dequeue conditions of pq, and add extra fields to the State class.
Below is the code. We add a k parameter to the dijkstra function. Other changes are highlighted: