Bir şebekede en kısa yol problemi için yeni bir yaklaşım

Yöneylem araştırması ve endüstri mühendisliğinde bilinen bir problem olan En Kısa Yol Problemi, Çizge Kuramının da uygulamada en çok kullanılan problemlerinden biridir. En Kısa Yol Problemi, verilen iki nokta arasındaki yollar içinden uzunluğu en kısa yolu bulma ya da verilen bir düğümden başlayan ve diğer tüm düğümlere ulaşan yollar içinden en kısa uzunlukta olan yolun bulunması olarak tanımlanır. Çizgenin düğüm sayısının büyük olduğu durumlarda bu çizgeyi alt çizgelere ayırarak problemi çözme, bilinen bir yöntemdir. Verilen çizge, düğümleri sayısı hemen hemen eşit ve kesim kirişlerinin ağırlıktan toplamı minimum olacak biçimde parçalanna aynlır. Bu çalışmada ilk olarak çizge kuramının temel kavranılan verilmiş, ardından en kısa yol problemi için iki adet algoritma birer uygulama ile sunulmuş, çizge parçalama için Kemighan Lin algoritması ve merkezleştirilmiş ağırlıklı aynt algoritmaları ele alınmıştır. Son olarak ise en kısa yol probleminin uygulanacağı çizge önce, Kemighan-Lin algoritması ile yukarıdaki kurallara uygun biçimde parçalanna aynlmış, sonra yolun başlangıç düğümü ve son düğümü dikkate alınarak, bir zincir çizge haline getirilmiş, her parça içinde amaç düğümlerle ilişkiyi sağlayacak biçimde en kısa yollar hesaplanmış, ardından bunlann geçiş kirişleri ile birleştirilmesi yöntemiyle amaç düğümler arasındaki en kısa yolu bulan bir algoritma geliştirilmiştir.