En Kısa Yol Probleminde Optimizasyon Algoritmalarının Performans Değerlendirmesi Üzerine Bir Çalışma
Tezin Türü: Yüksek Lisans
Tezin Yürütüldüğü Kurum: Ankara Yıldırım Beyazıt Üniversitesi, Fen Bilimleri Enstitüsü, Bilgisayar Mühendisliği Ana Bilim Dalı, Türkiye
Tezin Onay Tarihi: 2020
Tezin Dili: İngilizce
Öğrenci: Elçin Duygu EKMEN
Danışman: FATİH VEHBİ ÇELEBİ
Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
Özet:İki nokta arasındaki en kısa yolun en kısa sürede ya da en az maliyetle bulunması pek çok alanda oldukça önemlidir. En kısa yol problemi graf üzerindeki bir başlangıç düğümünden hedef düğümüne en kısa yoldan gitmeyi amaçladığından günümüzde trafik uygulamalarında, internet trafiğinin yönlendirilmesi ve oyun programlamada sıklıkla kullanılmaktadır. Zaman geçtikçe, bilim ve teknolojinin gelişmesiyle birlikte, birçok bilim insanı en kısa yol problemini çözmek için araştırmalar yapmış, birçok algoritma geliştirilmiştir. Farklı türdeki problemlere hitap eden bu algoritmalarla, düğümler arasındaki en kısa yollar bulunabilmektedir. Literatürde en kısa yol problemine ilişkin oldukça fazla sayıda ve farklı çalışmalar yer aldığı gözlenmiştir. Bu çalışmanın amacı en kısa yol problemlerinde kullanılan algoritmalardan dördünün analiz edilmesi ve karşılaştırılmasıdır. Projede Dijkstra Algoritması, Bellman–Ford Algoritması, Johnson's Algoritması ve Floyd-Warshall Algoritmasının ekranda çizilen bir graf için, başlangıç ve bitiş noktası belirlenerek hangi sürede ve hangi maliyet ile en kısa yolu bulabildiği tespit edilmiştir. En kısa yolun belirlenmesinde hangi algoritmanın daha iyi ve etkili olduğu tartışılmıştır. 4 farklı algoritmanın tamamiyle bağlı, pozitif ağırlıklı kenarlardan oluşan ve yönsüz graflar için, aynı simulasyon ile kıyaslanması daha önce karşılaşılmamış bir çalışma olması nedeni ile önem taşımaktadır. Çalışma sonuçlarına göre, kullanılacak algoritmanın graf veya problem türüne göre seçilmesi gerektiği anlaşılmıştır. Ancak; bağlı, pozitif ağırlıklı kenarlardan oluşan ve yönsüz graflar için kesinlikle Dijkstra algoritması kullanılması gerektiği gözlenmiştir. Anahtar Kelimeler: Graf, en kısa yol, optimizasyon, Dijkstra, Floyd-Warshall, Bellman-Ford, Johnson's