Algorithmes de recherche dans un graphe pondéré

Floyd-Warshall

Complexité : \( C_n = \mathcal{O}(|S|^3) \)

FCT FLOYD_WARSHALL(M : matrice d'adjacence d'un graphe pondéré) :
    POUR k ALLANT de 0 A |S| - 1 FAIRE :
        POUR i ALLANT DE 0 A |S| - 1 FAIRE :
            POUR j ALLANT de 0 A |S| - 1 FAIRE :
                M_{i,j} <- min(M_{i,j}, M_{i,k} + M_{k,j})
            FIN POUR
        FIN POUR
    FIN POUR
FIN FCT

Dijkstra

Complexité : \( C_n = \mathcal{O}((|S| + |A|)log(|S|)) \)

FCT DIJKSTRA(G : graphe pondéré, dep : sommet de départ) :
    vus <- {}
    a_traiter <- file de priorité vide
    a_traiter <- enfiler dep de priorité 0
    distance <- structure qui associe à dep 0 et aux autres sommets +∞
    TANT QUE a_traiter non vide FAIRE :
        s <- defiler de a_traiter le sommet de priorité minimale
        SI s ∉ vus ALORS :
            vus <- vus U {s}
            POUR chaque voisin v de s dans G FAIRE :
                SI distances[v] > distances[s] + ω(s,v) ALORS :
                    disntaces[v] <- distances[s] + ω(s,v)
                    a_traiter <- enfiler v
                FIN SI
            FIN POUR
        FIN SI
    FIN TANT QUE
FIN FCT