Finding optimal paths in a graph
Consider that you are driving back home. You have in mind information about roads that you need to take in order to go from your office to your sweet home, and you can provide a measure of time you'll spend on each one of these roads, considering the distance covered and the amount of traffic you'll likely run into by taking it. How are you going to determine the best path home? This problem of yours falls under the class of problems to find the shortest path, and for this recipe, we are going to solve this problem using the Dijkstra algorithm.
Given a graph, the Dijkstra's algorithm proceeds by visiting one currently unvisited node at every iteration, considering all its neighbors, and computing values that represent ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access