EN KISA YOL PROBLEMİNDE ÇİZGE PARÇALAMA YÖNTEMİ KULLANILARAK YENİ BİR YAKLAŞIM

Bu çalışmada ilk olarak çizge kuramının temel kavramları verilmiş, en kısa yol problemi tanıtılmış ve ayrıca çizge parçalama için Kernighan Lin algoritması ele alınmıştır. Asıl amaç olarak, en kısa yol problemi için çizgeyi Kernighan Lin algoritması kurallarına göre işlemcilere ayıran ve böylelikle problem için çizgeyi başlangıç ve bitiş noktalarını ele alan bir zincir çizge formuna dönüştürerek en kısa yolu bulan bir yaklaşım ortaya konulmuştur. Her parça içinde amaç düğümler arasındaki en kısa rotayı bulan parça içi en kısa yollar hesaplanmaktadır

As a starting point of this study, basic concepts of graph theory, shortest path problem, and Kernighan Lin algorithm are presented for graph partitioning problem. Main aim is to present an approach which solves the shortest path problem by using the graph partitioning technique in regard with the rules of Kernighan-Lin algorithm; therefore it becomes to a chain graph dealing with the starting and the target nodes of the problem. The shortest paths are calculated in order to provide the shortest route between the objective nodes in all the processors.