Floyd-Warshall algoritması

Bilgisayar biliminde, Floyd-Warshall algoritması kenar ağırlıkları artı ya da eksi değere sahip (ancak eksi değerli döngüsü olmayan) çizgelerde en kısa yolları bulma algoritmasıdır.^[1][2] Algoritma uygulandığında her düğüm çifti için en kısa yol uzunluklarını bulur. Özgün algoritma yol detaylarını döndürmese de, küçük değişikliklerle yolların oluşturulması da mümkündür. Çizge kuramında ve diğer matematik uygulamalarında kullanılır.

Floyd-Warshall algoritması
Sınıf	Tüm-çiftler için en kısa yol problemi (ağırlıklı çizgeler)
Zaman karmaşıklığı	${\displaystyle \Theta (|V|^{3})}$
En iyi	${\displaystyle \Theta (|V|^{3})}$
Ortalama	${\displaystyle \Theta (|V|^{3})}$
Alan karmaşıklığı	${\displaystyle \Theta (|V|^{2})}$

Ayrıca bakınız

• Dijkstra algoritması
• A* arama algoritması
• Prim algoritması
• Bellman-Ford algoritması