Floyd-Warshall algoritması

Floyd-Warshall algoritması
Sınıf	Tüm-çiftler için en kısa yol problemi; (ağırlıklı çizgeler)
Zaman karmaşıklığı
En iyi
Ortalama
Alan karmaşıklığı

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.

Ayrıca bakınız

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

Kaynakça

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (1990). Introduction to Algorithms (1 bas.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8. Bkz. Bölüm 26.2, "The Floyd–Warshall algorithm", s. 558–565 ve Bölüm 26.4, "A general framework for solving path problems in directed graphs", s. 570–576.
Kenneth H. Rosen (2003). Discrete Mathematics and Its Applications, 5th Edition. Addison Wesley. ISBN 978-0-07-119881-3.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (1990). Introduction to Algorithms (1 bas.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8. Bkz. Bölüm 26.2, "The Floyd–Warshall algorithm", s. 558–565 ve Bölüm 26.4, "A general framework for solving path problems in directed graphs", s. 570–576.

[2] Kenneth H. Rosen (2003). Discrete Mathematics and Its Applications, 5th Edition. Addison Wesley. ISBN 978-0-07-119881-3.