Shortest Path Problem Algorithm in Network Based on Matrix Multiplication
Liu Li-hua · Dianzi xuebao · 2009
Shortest Path Problem in network can be acted as a model for many application problems,but the iteration process of the conventional solution algeorithm is complex.In this paper,the shortest path algorithm based on the matrix multiplication in a weighted-graph are described,and its time complexity is as same as Dijkstra algorithm.In a given network graph,this algorithm delete spare nodes or edges and reach the goal that reduced network graph and improved speed of solving problem under the condition of unchanged shortest parth.Finally,we give examples,e.g.Traveling Salesman Problem,shortest path problem,to illistrate its advanteges,possessing merits of simple operation and easy understanding,compared with dynamic programming technology.