𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Distributed Algorithm for Shortest Paths

✍ Scribed by Chen, C.C.

Book ID
114606602
Publisher
IEEE
Year
1982
Tongue
English
Weight
430 KB
Volume
C-31
Category
Article
ISSN
0018-9340

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A fully dynamic algorithm for distribute
A fully dynamic algorithm for distributed shortest paths
✍ Serafino Cicerone; Gabriele Di Stefano; Daniele Frigioni; Umberto Nanni πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 297 KB

We propose a fully dynamic distributed algorithm for the all-pairs shortest paths problem on general networks with positive real edge weights. If is the number of pairs of nodes changing the distance after a single edge modiΓΏcation (insert, delete, weight decrease, or weight increase) then the messa

A self-stabilizing algorithm for the sho
A self-stabilizing algorithm for the shortest path problem in a distributed system
✍ Tetz C. Huang; Ji-Cherng Lin πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 352 KB

In this paper, we propose a self-stabilizing algorithm for finding shortest paths in a distributed system in which a central daemon is assumed. The correctness of the proposed algorithm is proved by using the bounded function technique.

A self-stabilizing algorithm for the sho
A self-stabilizing algorithm for the shortest path problem assuming the distributed demon
✍ Tetz C. Huang πŸ“‚ Article πŸ“… 2005 πŸ› Elsevier Science 🌐 English βš– 1015 KB

Shortest path finding has a variety of applications in transportation and communication. In this paper, we study a well-known self-stabilizing algorithm for the shortest path problem for the distributed systems. The prevlotm works on this topic had two assumptions that can be relaxed in this paper.

A distributed shortest-paths algorithm w
A distributed shortest-paths algorithm with distance-dependent message complexities
✍ Kouji Miura; Toshimitsu Masuzawa; Nobuki Tokura πŸ“‚ Article πŸ“… 1994 πŸ› John Wiley and Sons 🌐 English βš– 948 KB

## Abstract This paper presents a distributed algorithm for the single‐source shortest‐paths problem in a network with nonnegative integral link weights. Its message complexity is , where __n__ is the number of processors, __e__ is the number of links, and __D__ is the maximum distance from the ro