Dijkstra's algorithm

""" Dijkstra's Algorithm finds the shortest path between a given node (which is called the "source node") and all other nodes in a graph.

A* algorithm is just like Dijkstra's algorithm, and the only difference is that A* tries to look for a better path by using a heuristic function, which gives priority to nodes that are supposed to be better than others while Dijkstra's just explore all possible ways.

Mnemonic summary: Dijkstra is a BFS with three changes:
 - edges are 2-tuples
   - The edge entries in the graph are 2-tuples rather than just vertex values or Node objects. Each edge entry has a second 'distance/weight' integer value.
 - a heap is used
   - A heap is used rather than a deque. The heap value is a 2-tuple with the distance first, then the vertex
 - another dict tracks shortest distance to each vertex
"""
import heapq

def dijkstra(graph, start):
    total_distance_to = {vertex: float('infinity') for vertex in graph}
    total_distance_to[start] = 0

    hp = [(0, start)]  # (distance, vertex)  # Heap to hold vertices to be processed
    while hp:
        current_vertex_distance, current_vertex = heapq.heappop(hp)  # Get vertex with smallest distance
        if current_vertex_distance > total_distance_to[current_vertex]:  # Only process a vertex once
            continue

        # Most of the logic is in the neighbor-handling block
        for neighbor, marginal_distance in graph[current_vertex]:  # If a shorter path is found
            total_neighbor_distance = current_vertex_distance + marginal_distance
            if total_neighbor_distance < total_distance_to[neighbor]:
                total_distance_to[neighbor] = total_neighbor_distance

                # Any time we find a shorter distance to a vertex, we want to recalculate the distances to its neighbors.
                heapq.heappush(hp, (total_neighbor_distance, neighbor))
    return total_distance_to

graph = {
    'a': [('b', 1), ('c', 2)],
    'b': [('d', 3), ('e', 4)],
    'c': [],
    'd': [],
    'e': []
}
print(dijkstra(graph, 'a'))