Computing Shortest Path Problem with Subtractive Weight Based on Tableau Method
Xiamiao Li, Jie Tang, Ming-Ming Qi · 2007
Dijkstra algorithm is regarded as the most classical method to settle the shortest path problem. But its ability would be not equal to case where subtractive-weight exists. This thesis raises an improved algorithm based on Dijkstra, but treats P-sign as an alterable sign as T-sign. The algorithm can commendably achieve the calculation assignment, but not form subtractive cycles or zero cycles in graph. It is based on tableau method to make the graph cleaner than graphic method, and calculate subtractive weight problems more effectively.