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 distances to these neighbors if one used the current node to reach them. If, for any neighbor, the value computed is better than any value already held by it, that is, the value is already computed when it was previously visited...