Dijkstra Algorithm with Restrictions

In the last article Dijkstra Algorithm Principles and Implementation, we derived Dijkstra's algorithm from the standard BFS algorithm to solve the shortest path problem in weighted graphs.

In this article, we will look at a more complex situation: the shortest path problem with constraints.

This type of problem is more complicated than the standard shortest path problem, but don't worry. You only need to make a small change to the Dijkstra template to solve it. So please make sure you fully understand the last chapter.

Shortest Path Problem with Constraints

In the previous chapter, the Dijkstra algorithm used the third version of Three Ways to Write BFS. Each node keeps its own State object, so we can easily extend the standard Dijkstra algorithm to handle more complex tasks.

For example, now you are not only asked to find the shortest path, but also to make sure the path has no more than k edges.

You can still use Dijkstra's algorithm for this, but you need to change the conditions for adding and removing from the pq, and add extra fields to the State class.

Below is the code. We add a k parameter to the dijkstra function. Other differences are highlighted:

Key Changes

Optimization for Point-to-Point Shortest Path