Algorithme de Floyd

Besoin

Algorithme de PCC

Analyse

À partir d'un sommet de départ, examiner l'ensemble des noeuds les plus proches, plus l'ensemble des noeuds un niveau plus loin, etc.

Conception

Parcours du graphe en largeur d'abord.

Polynomial.

Exemples

• Routage internet (OSPF, IS-IS)

Notes

• Complexité en O(n³)
• Version améliorée par Dijkstra en O(a² log(n)) pour des coûts >= 0

Références

• Athanasios, Papagelis: "Dijkstra algorithm", You just found... my message in Cyberspace Ocean