Shortest path

A graph is a great data structure for storing the 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 locations, 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 distance from a starting node to all nodes located in the graph. Then, you can easily get not only the cost of 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, namely for storing an identifier of the previous node—the node from which the current node can be reached with the smallest overall cost, as well as the minimum distance...