Dijkstra Algorithm with Restrictions

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

This article will discuss a more complex situation: the shortest path problem with restrictions.

These problems are more complex than the standard shortest path problem, but don't worry. You just need to make small changes to the Dijkstra template we learned before. So please make sure you have fully understood the previous chapter.

Shortest Path Problems with Restrictions

In the last chapter, the Dijkstra algorithm we used was the third version from Three Ways to Write BFS. Each node keeps its own State object, which makes it easy to extend the standard Dijkstra algorithm to handle more complex tasks.

For example, now you need to find not just the shortest path, but also make sure the path uses at most k edges.

You can still use the Dijkstra algorithm for this, but you need to modify the distTo array and add more fields to the State class.

Below is the direct code implementation. We add a k parameter to the dijkstra function. The other changes are marked and highlighted:

Optimizing Point-to-Point Shortest Path