Shortest path problem with uncertain arc lengths

Shortest path problem with uncertain arc lengths

0.00 Avg rating0 Votes
Article ID: iaor20119226
Volume: 62
Issue: 6
Start Page Number: 2591
End Page Number: 2600
Publication Date: Sep 2011
Journal: Computers and Mathematics with Applications
Authors:
Keywords: combinatorial optimization, networks
Abstract:

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 α equ1‐shortest path and the most shortest path in an uncertain network. It points out that there exists an equivalence relation between the α equ2‐shortest path in an uncertain network and the shortest path in a corresponding deterministic network, which leads to an effective algorithm to find the α equ3‐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.

Reviews

Required fields are marked *. Your email address will not be published.