A new approach for the shortest path problem in a network

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.