Plus court chemin : 15 arêtes
fx-50FH II · CMPLX · 547 bytes
Trouver un chemin de coût minimal dans un réseau non orienté de dix sommets et 15 arêtes au maximum ; afficher les sommets puis le coût total.
- 547 octets
- Mode CMPLX
Exemples corrigés
Exemple 1
Exercice universitaire original : un robot de musée parcourt des salles numérotées. Les liaisons sont bidirectionnelles et les coûts sont des minutes. Trouver un chemin de durée minimale de 2 à 6 et sa durée totale.
Toutes les arêtes sont non orientées ; les liaisons non indiquées n'existent pas. Liste (a–b : coût) : 2–1: 7; 2–3: 4; 1–4: 5; 3–4: 2; 3–5: 8; 4–6: 3; 5–6: 2; 1–5: 12
Réponse
Solution standard (sans calculatrice)
- Appliquer Dijkstra depuis S. u est le sommet nouvellement fixé, d(v) une distance provisoire mise à jour, ∞ une distance encore inaccessible.
- u=2, d(2)=0; d(1)=7, d(3)=4
- u=3, d(3)=4; d(4)=6, d(5)=12
- u=4, d(4)=6; d(6)=9
- u=1, d(1)=7; ∅
- u=6, d(6)=9; d(5)=11
- Remonter les prédécesseurs et additionner directement les coûts : 2 → 3 → 4 → 6; Coût total 4+2+3=9 min
Exemple 2
Exercice universitaire original : une navette d'exposition utilise des tarifs entiers. La liaison 7–8 est gratuite, de coût exactement 0. Trouver un chemin de tarif minimal de 7 à 2 et son tarif total.
Toutes les arêtes sont non orientées ; les liaisons non indiquées n'existent pas. Liste (a–b : coût) : 7–8: 0; 8–9: 3; 9–2: 4; 7–1: 9; 1–2: 2; 8–2: 10; 9–1: 1
Réponse
Solution standard (sans calculatrice)
- Appliquer Dijkstra depuis S. u est le sommet nouvellement fixé, d(v) une distance provisoire mise à jour, ∞ une distance encore inaccessible.
- u=7, d(7)=0; d(1)=9, d(8)=0
- u=8, d(8)=0; d(2)=10, d(9)=3
- u=9, d(9)=3; d(1)=4, d(2)=7
- u=1, d(1)=4; d(2)=6
- u=2, d(2)=6; ∅
- Remonter les prédécesseurs et additionner directement les coûts : 7 → 8 → 9 → 1 → 2; Coût total 0+3+1+2=6
Exemple 3
Exercice universitaire original : un réseau de communication pédagogique relie dix terminaux virtuels. Chaque liaison bidirectionnelle a un coût entier fixe de transmission. Saisir les 15 liaisons dans l’ordre, dernières comprises, et trouver un chemin de coût minimal de 1 à 10 ainsi que son coût total.
Toutes les arêtes sont non orientées ; les liaisons non indiquées n'existent pas. Liste (a–b : coût) : 1–2: 5; 2–3: 7; 3–4: 4; 4–5: 6; 5–6: 3; 6–7: 8; 7–8: 2; 8–9: 5; 9–10: 4; 1–6: 9; 2–7: 9; 3–8: 9; 4–9: 9; 5–10: 9; 2–9: 1
Réponse
Solution standard (sans calculatrice)
- Appliquer Dijkstra depuis S. u est le sommet nouvellement fixé, d(v) une distance provisoire mise à jour, ∞ une distance encore inaccessible.
- u=1, d(1)=0; d(2)=5, d(6)=9
- u=2, d(2)=5; d(3)=12, d(7)=14, d(9)=6
- u=9, d(9)=6; d(4)=15, d(8)=11, d(10)=10
- u=6, d(6)=9; d(5)=12
- u=10, d(10)=10; ∅
- Remonter les prédécesseurs et additionner directement les coûts : 1 → 2 → 9 → 10; Coût total 5+1+4=10
Quand l’utiliser
Mathématiques universitaires · recherche opérationnelle. Réseau fixe, coûts non négatifs et additifs. Aucune direction physique ni condition de circulation n'est déduite.
Saisir le réseau
- Au premier Y?, saisir S+Ti : S est le départ et T l'arrivée. Alterner ensuite Y? = a+bi pour une arête non orientée et M? = son coût. i s'obtient avec ENG. Ne pas saisir le nombre de sommets ou d'arêtes.
- Terminer par EXE seul au prochain Y?, puis EXE seul à M?. Il s'agit de deux invites différentes. Un coût nul connu exige 0EXE.
Lire le chemin et le coût
- Chaque écran Disp donne un sommet depuis S. Appuyer sur EXE après chaque sommet, y compris T, pour atteindre le coût final. −1 signifie aucun chemin. S=T affiche S puis 0. Quitter par AC ; EXE relance le programme.
Conditions et limites
- Sommets entiers 1–10, coûts entiers 0–100, au plus 15 arêtes hors boucles. Chaque arête parallèle occupe une place. Employer une même unité de coût.
- La version à 15 arêtes ne vérifie pas entièrement les bornes des sommets ni les coûts entiers. Respecter le domaine. Coût négatif ou manquant et dépassement : Math ERROR. Avant saturation, extrémités absentes avec coût non négatif et boucles sont ignorées. Une fois pleine, seule la paire vide termine la saisie.
- Le programme occupe 547 des 680 bytes partagés, laissant 133 bytes aux autres zones. Chaque exécution efface A, B, C, D, X, Y, M et Ans ; sauvegarder les valeurs utiles.
- Créer et exécuter en CMPLX, a+bi et Norm 1. Exemples : Deg, P1. La fin normale rétablit Norm 1. i associe deux numéros entiers, pas un coût imaginaire.
- Arêtes orientées, poids négatifs et plus de dix sommets exclus. Un seul chemin est renvoyé en cas d'égalité, sans garantir le moins d'arêtes. Respecter le code exact : sa marge de précision est étroite.
Vérification de l’accès…