A Improving Method in the Shortest Path
Ma Na · 2003
The shortest path algorithms in directed graph D=(V,E) with negative weight is analyzed, and not all of the labels of subset Sk of V constructed by utilizing the Dijkstra algorithm are the weights for a shortest path between V1 and Vk is presented by giving a instance. It also indicated the Dijkstra algorithm is not adaptive for this case. The algorithm with recursive formula is for calculating the shortest path in directed graph with negative weight is inducted here. Finally, numerical example has shown the application of the method.