dijkstra.py

Note de lecture générée automatiquement

Le vrai fichier est scripts/maths/dijkstra.py (Obsidian n’affiche pas les scripts eux-mêmes). Ne modifie pas cette note : modifie le script, puis relance python3 generer_vues_obsidian.py dans le dossier scripts.

• À quoi il sert : Plus court chemin avec tableau d’étapes
• Lancer (dans le dossier scripts/maths/) : python3 dijkstra.py A F "A-B:4 A-C:2 C-B:1 …"
• Fiche : M07 - Graphes et plus court chemin
• Retour : 00 - Tous les scripts

Code

#!/usr/bin/env python3
"""
dijkstra.py — Plus court chemin (algorithme de Dijkstra) avec le tableau d'étapes
comme on le présente à l'examen.
 
Utilisation :
    python3 dijkstra.py A F "A-B:4 A-C:2 C-B:1 B-D:5 C-D:8 C-E:10 D-E:2 D-F:6 E-F:2"
    python3 dijkstra.py A F "A>B:4 ..."      (avec > : arc orienté ; avec - : arête)
"""
import heapq
import sys
 
 
def lire_graphe(texte: str) -> dict:
    graphe = {}
    for element in texte.split():
        liaison, poids = element.split(":")
        oriente = ">" in liaison
        origine, destination = liaison.split(">" if oriente else "-")
        graphe.setdefault(origine, {})[destination] = float(poids)
        graphe.setdefault(destination, {})
        if not oriente:
            graphe[destination][origine] = float(poids)
    return graphe
 
 
def dijkstra(graphe: dict, depart: str):
    distances = {s: float("inf") for s in graphe}
    predecesseurs = {s: None for s in graphe}
    distances[depart] = 0
    fixes = set()
    file_priorite = [(0, depart)]
    sommets = sorted(graphe)
    print("Étape | fixé | " + " | ".join(f"{s:^9}" for s in sommets))
    etape = 0
    while file_priorite:
        distance_courante, sommet = heapq.heappop(file_priorite)
        if sommet in fixes:
            continue
        fixes.add(sommet)
        for voisin, poids in graphe[sommet].items():
            if voisin not in fixes and distance_courante + poids < distances[voisin]:
                distances[voisin] = distance_courante + poids
                predecesseurs[voisin] = sommet
                heapq.heappush(file_priorite, (distances[voisin], voisin))
        cellules = []
        for s in sommets:
            if s in fixes and s != sommet:
                cellules.append("    -    ")
            elif distances[s] == float("inf"):
                cellules.append("    ∞    ")
            else:
                pred = predecesseurs[s] or "-"
                etoile = "*" if s == sommet else " "
                cellules.append(f"{distances[s]:>4g}({pred}){etoile}".center(9))
        print(f"{etape:^5} | {sommet:^4} | " + " | ".join(cellules))
        etape += 1
    return distances, predecesseurs
 
 
if __name__ == "__main__":
    if len(sys.argv) != 4:
        sys.exit(__doc__)
    depart, arrivee, texte_graphe = sys.argv[1], sys.argv[2], sys.argv[3]
    graphe_saisi = lire_graphe(texte_graphe)
    distances, predecesseurs = dijkstra(graphe_saisi, depart)
    chemin, sommet = [], arrivee
    while sommet is not None:
        chemin.insert(0, sommet)
        sommet = predecesseurs[sommet]
    print(f"\nPlus court chemin {depart} → {arrivee} : {' → '.join(chemin)}  (longueur {distances[arrivee]:g})")