Exercices de programmation pour classes préparatoires
Ecrire une fonction distance(graphe, depart, arrivee) qui renvoie la longueur du plus court chemin entre depart et arrivee dans un graphe non oriente non pondere (toutes les aretes ont un poids de 1). Si aucun chemin n'existe, renvoyer -1.
Representation : le graphe est represente par un dictionnaire d'adjacence {sommet: [voisins]}.
Indication : un parcours en largeur (BFS) depuis le sommet de depart permet de trouver les distances minimales vers tous les autres sommets.
| Appel | Résultat attendu |
|---|---|
| distance({0: [1, 2], 1: [0, 3], 2: [0], 3: [1]}, 0, 3) | 2 |
| distance({0: [1], 1: [0], 2: []}, 0, 2) | -1 |
Connectez-vous pour soumettre du code.