58. The shortest path between nodes

To solve the proposed problem you must use the Dijkstra algorithm for finding the shortest path in a graph. Although the original algorithm finds the shortest path between two given nodes, the requirement here is to find the shortest path between one specified node and all the others in the graph, which is another version of the algorithm.

An efficient way to implement the algorithm is using a priority queue. The pseudocode for the algorithm (see https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) is the following:

function Dijkstra(Graph, source):   dist[source] ← 0                 // Initialization    create vertex set Q   for each vertex v in Graph:       if v ≠ source dist[v] ← INFINITY // Unknown distance from source to v ...

Get Modern C++: Efficient and Scalable Application Development now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.