Shortest Path Problem with Uniform Distribution Weights
Pla Uni · Computer Engineering and Applications Journal · 2005
The shortest path problem(SP) is a basic problem in network design,which is NP-complete.Most research works of SP are based on the supposition that the weights on edges are determinate numbers currently.The paper studies the SP with non-determinate weights on edges.A fuzzy linear integer-programming model(FIP) is established,which has a uniform distribution parameter in object function.Applying the positive and negative idea point,FIP can be transformed into a linear integer programming with a single determinate objective function.A new algorithm is presented and is proved to have a polynomial time complexity.The efficiency of the algorithm is demonstrated by simulating example.