A New Algorithm for the Shortest Path Problems in a Directed Graph with Negative Weights
Xin Wang · 2007
The Dijkstra algorithm is a classical way for finding the shortest path,but it is not able to solve the shortest path problems with negative weights.This paper studies the shortest path problems with negative weights and brings forward a new algorithm to change a shortest path problem with negative weights to a shortest way problem with nonnegative weights.Finally we use the Dijkstra algorithm to solve the problem and the validity of the method is demonstrated by an example.Eventually the algorithm has some practical meaning.