A Distributed Shortest Path Protocol.

Abstract

We present a distributed protocol for obtaining the shortest paths between all pairs of nodes in a network with weighted links. The protocol is based on an extension of the Dijkstra (centralized) shortest path algorithm and uses collaboration between neighboring nodes to transfer the information needed at the nodes for the successive construction of the shortest paths. A formal description of the protocol is given by indicating the exact algorithm performed by each node. The validation proofs are greatly simplified by separating the communication mechanism from the computation at the nodes, the latter being the transposition of the Dijkstra shortest path algorithm to the decentralized protocol. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1981
Accession Number
ADA101685

Entities

People

  • Adrian Segall
  • Francine B. M. Zerbib

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Buildings And Structures
  • Classification
  • Computations
  • Computer Science
  • Determinants (Mathematics)
  • Electrical Engineering
  • Engineering
  • Identities
  • Information Systems
  • Military Research
  • Notation
  • Validation

Fields of Study

  • Computer science

Readers

  • Computer Networking
  • Computer Programming and Software Development.