Shortest path
A graph is a great data structure for storing data of various maps, such as cities and the distances between them. For this reason, one of the obvious real-world applications of graphs is searching for the shortest path between two nodes, which takes into account a specific cost, such as the distance, the necessary time, or even the amount of fuel required.
There are several approaches to the topic of searching for the shortest path in a graph. However, one of the common solutions is Dijkstra’s algorithm, which makes it possible to calculate the distance from a starting node to all nodes located in the graph. Then, you can easily get not only the cost of the connection between two nodes but also find nodes that are between the start and end nodes.
Dijkstra’s algorithm uses two auxiliary node-related arrays:
- One for storing an identifier of the previous node, which is the node from which the current node can be reached with the smallest overall...
