Shortest distance and reliability of probabilistic networks

Research output: Contribution to journalArticlepeer-review

116 Scopus citations


When the "length" of a link is not deterministic and is governed by a stochastic process, the "shortest" path between two points in the network is not necessarily always composed of the same links and depends on the state of the network. For example, in communication and transportation networks, the travel time on a link is not deterministic and the fastest path between two points is not fixed. This paper presents an algorithm to compute the expected shortest travel time between two nodes in the network when the travel time on each link has a given independent discrete probability distribution. The algorithm assumes the knowledge of all the paths between two nodes and methods to determine the paths are referenced. In reliability (i.e. the probability that two given points are connected by a path) computations, associated with each link is a probability of "failure" and a probability of "success". Since "failure" implies infinite travel time, the algorithm simultaneously computes reliability. The paper also discusses the algorithm's capability to simultaneously compute some other performance measures which are useful in the analysis of emergency services operating on a network.

Original languageEnglish (US)
Pages (from-to)347-355
Number of pages9
JournalComputers and Operations Research
Issue number4
StatePublished - Dec 1976
Externally publishedYes

ASJC Scopus subject areas

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research


Dive into the research topics of 'Shortest distance and reliability of probabilistic networks'. Together they form a unique fingerprint.

Cite this