Bir şebekede en kısa yol problemi için yeni bir yaklaşım
A new approach for the shortest path problem in a network
Yazar: MUSTAFA KEMAL BEŞER
Danışman: Y.DOÇ.DR. SAMİM DÜNDAR
Dokuz Eylül Üniversitesi / Sosyal Bilimler Enstitüsü / Ekonometri Ana Bilim Dalı
Derece: Yüksek Lisans, 2000
Konu: Ekonometri = Econometrics
Dizin: Algoritmalar = Algorithms ; En kısa yol problemi = Shortest path problem ; Grafik bölümleme = Graph partitioning ; Grafikler = Graphics ; Yöneylem araştırması = Operations research

Özet:
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.

Abstract:
Shortest Path Problem, which is well known in Industrial Engineering and Operational Research, is one of the most encountered problems of Graph Theory in application. Shortest Path Problem is defined as finding the shortest way between two given nodes or finding the shortest path from which begins from a given node and arrives to all given nodes. If the node numbers of the graph is so much, then solving problem by separating this graph to processors is an appropriate method. The given graph is separated to parts as the processors are balanced and the cutsize would be minimum. In this study, first of all basic concepts of Graph Theory is given, then two algorithms for the Shortest Path Problem are presented with an application and dealt with Kernighan Lin Algorithm to partition the graph. Finally, the graph which Shortest Path Problem would be applied on was partitioned into pieces in regard with the rules above with Kernighan-Lin Algorithm, then converted to a chain graph dealing with the starting node and target node of the problem. In all the processors, the shortest paths are calculated in order to provide relation with objective nodes and then an algorithm which finds the shortest path between objective nodes is developed by the method of uniting these with cutting edges.