Random variables as arc parameters when solving shortest path problems

Deolinda Rasteiro, Nelson Chibeles-Martins

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review


Random graph theory was initially proposed by Paul Erdős and Alfred Rényi in the 1950s. A book of Béla Bollobás presented the first systematic and extensive group of results of random graphs. Associating to each edge of a random graph a real random variable, we obtain a probabilistic network. The determination of an optimal path between two nodes in a probabilistic network has first been studied by H. Frank in 1969. Since then few theoretical results have been found, even though there is a recognizable applicability of this type of networks to real problems, namely, social and telecommunication networks.

The mathematical model proposed in this chapter maximizes the expected value of a utility function over a directed random network, where the costs related to the arcs are real random variables following Gaussian distributions.

We consider the linear, quadratic, and exponential utility functions, presenting a theoretical formulation based on multicriterion models, as well as the resulting algorithms that may be applied to real-life problems. In the last section an application to a real problem that was developed to solve a criminality problem in the city of Lisbon is discussed. Due to its complexity these types of applications are suggested to use as project-based learning and not as an easy applied exercise to solve within a limited time.
Original languageEnglish
Title of host publicationCalculus for Engineering Students: Fundamentals, Real Problems, and Computers
EditorsJesús Martín-Vaquero, Michael Carr, Araceli Queiruga-Dios, Daniela Richtáriková
PublisherAcademic Press
ISBN (Print)978-0-12-817210-0
Publication statusPublished - 2020

Publication series

NameMathematics in Science and Engineering
PublisherAcademic Press


  • networks
  • shortest path
  • arc parameter
  • probability distribution
  • optimality principles
  • applications in real problems


Dive into the research topics of 'Random variables as arc parameters when solving shortest path problems'. Together they form a unique fingerprint.

Cite this