Exercices de programmation pour classes préparatoires
Ecrire une fonction dijkstra(graphe, depart, arrivee) qui renvoie la distance du plus court chemin entre le sommet depart et le sommet arrivee dans un graphe pondere.
Representation : le graphe est represente par un dictionnaire d'adjacence pondere {sommet: [(voisin, poids)]}. Par exemple {'A': [('B', 1), ('C', 4)], 'B': [('C', 2)], 'C': []} represente un graphe oriente ou l'arete de A vers B a un poids de 1, celle de A vers C un poids de 4, et celle de B vers C un poids de 2.
Si le depart et l'arrivee sont le meme sommet, la distance est 0. Tous les poids sont positifs ou nuls.
(Optionnel : Vous pouvez utiliser le module heapq pour implementer la file de priorite.)
| Appel | Résultat attendu |
|---|---|
| dijkstra({'A': [('B', 1), ('C', 4)], 'B': [('C', 2)], 'C': []}, 'A', 'C') | 3 |
| dijkstra({'A': [('B', 1)], 'B': []}, 'A', 'A') | 0 |
| dijkstra({'A': [('B', 5)], 'B': []}, 'A', 'B') | 5 |
Connectez-vous pour soumettre du code.