Journal
COMPUTERS & MATHEMATICS WITH APPLICATIONS
Volume 62, Issue 6, Pages 2591-2600Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.camwa.2011.07.058
Keywords
Shortest path problem; Uncertainty theory; Uncertain programming; Dijkstra algorithm
Categories
Funding
- National Natural Science Foundation of China [60874067, 91024032]
Ask authors/readers for more resources
Uncertainty theory provides a new tool to deal with the shortest path problem with nondeterministic arc lengths. With help from the operational law of uncertainty theory, this paper gives the uncertainty distribution of the shortest path length. Also, it investigates solutions to the a-shortest path and the most shortest path in an uncertain network. It points out that there exists an equivalence relation between the alpha-shortest path in an uncertain network and the shortest path in a corresponding deterministic network, which leads to an effective algorithm to find the alpha-shortest path and the most shortest path. Roughly speaking, this algorithm can be broken down into two parts: constructing a deterministic network and then invoking the Dijkstra algorithm. (C) 2011 Elsevier Ltd. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available