Plus court chemin : algorithme de Dijkstra

On considère un graphe pondéré (à poids positifs) représenté par un dictionnaire de listes d'adjacence avec poids.

Implémenter l'algorithme de Dijkstra qui, à partir d'un sommet source, calcule la distance minimale vers tous les autres sommets.

G = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', 2), ('D', 5)],
    'C': [('D', 1)],
    'D': []
}
>>> dijkstra(G, 'A')
{'A': 0, 'B': 1, 'C': 3, 'D': 4}