veri yapıları logo

Graflarda En Kısa Yol Ağacı Algoritmaları

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.

kruskal algoritması örnek

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.

dijkstra algoritması örnek

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.

Bir cevap yazın