Finding the shortest path in network with variable arc length and probabilistic nodes

In this paper, an innovative algorithm is presented to determine the shortest path in stochastic network. In the network, the presence of nodes is probabilistic and the arc lengths are random variables; each intermediate node i with the probability Pi is available and with the probability 1-Pi is removed from the network while the arc length can have different probability distribution functions including normal, uniform and exponential. The expected value of all possible paths from source node to sink node are clarified and finally the path with least expected value is identified as the shortest path.

کلیدواژه ها:

stochastic network ، shortest path ، probabilistic nodes