Merhaba arkadaşlar, bu yazımda önceki yazımın devamı niteliğinde bir yazı ele alacağım. Ağırlıklı, ağırlıksız, yönlü ve yönsüz graflarda dolaşmak için çeşitli algoritmalar geliştirilmiştir.
Kruskal Algoritması
En az maliyetli iki düğüm birleştirilir. Bu şekilde sıra ile küçükten büyüğe birleştirme işlemi yapılarak tüm düğümler gezilir. Bu şekilde ağaç oluşturulur. Basit bir algoritmadır.
Yukarıdaki örnekte en az maliyetli A-D ve C-E kenarları birleştirilmiş. Daha sonra en az maliyetli olan D-F arası birleştirilmiştir. Daha sonra maliyetli 7 olan kenarlar birleştirilecektir.
Prim’in Algoritması
Burada da en küçük maliyetli kenardan başlanır. Gidilen düğümden sonra en az maliyetle gidilecek diğer düğüm seçilir.
Sollin’in Algoritması
En az maliyetle olan düğümler seçilir ve daha sonra iki ağaç oluşturulur. İki ağacın birleşimi ile tek ağaç olmuş olur.
Dijkstra Algotirması
Ağırlıklı ve yönlü graflar için geliştirilmiş olup, negatif ağırlıklı kenarlarda çalışmamaktadır.
Yukarıdaki gibi bir tablo üzerinde de ata düğüm ve maliyetler de yazılmaktadır. Eğer açılan bir düğüme tekrar geliniyor ve maliyeti daha düşük ise o yol ele alınmaktadır.
Bellman ve Ford Algoritması
Dijkstra algoritmasının yetersiz kaldığı negatif ağırlıklı yollarda çözüm için geliştirilmiştir. Bu algoritmada da değerler tablo üzerine yazılır ama ataları yazılmamaktadır.
Floyd Algoritması
Dijskta gibi çalışır. Sürekli gidilen düğümde toplam maliyeti güncellemektedir. Düğümler ve yollar matrisleri oluşturulur. Velhasıl kullanımı zordur.
Umarım faydalı olmuştur.