𝔖 Bobbio Scriptorium
✦   LIBER   ✦

All-pairs shortest-paths computation in the presence of negative cycles

✍ Scribed by Kurt Mehlhorn; Volker Priebe; Guido Schäfer; Naveen Sivadasan

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
49 KB
Volume
81
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

We present an algorithm that solves the all-pairs shortest-paths problem on a directed graph with n vertices and m arcs in time O(nm + n 2 log n), where the arcs are assigned real, possibly negative costs. Our algorithm is new in the following respect. It computes the distance µ(v, w) between each pair v, w of vertices even in the presence of negative cycles, where µ(v, w) is defined as the infimum of the costs of all directed paths from v to w.

📜 SIMILAR VOLUMES

On the Exponent of the All Pairs Shortes
On the Exponent of the All Pairs Shortest Path Problem
✍ Noga Alon; Zvi Galil; Oded Margalit 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 900 KB

The upper bound on the exponent, |, of matrix multiplication over a ring that was three in 1968 has decreased several times and since 1986 it has been 2.376. On the other hand, the exponent of the algorithms known for the all pairs shortest path problem has stayed at three all these years even for t

On the All-Pairs-Shortest-Path Problem i
On the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs
✍ R. Seidel 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 318 KB

We present an algorithm, APD, that solves the distance version of the all-pairs-shortest-path problem for undirected, unweighted \(n\)-vertex graphs in time \(O(M(n) \log n)\), where \(M(n)\) denotes the time necessary to multiply two \(n \times n\) matrices of small integers (which is currently kno

On the all-pairs shortest-path algorithm
On the all-pairs shortest-path algorithm of Moffat and Takaoka
✍ Kurt Mehlhorn; Volker Priebe 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 3 views

We review how to solve the all-pairs shortest-path problem in a nonnegatively Ž 2 . weighted digraph with n vertices in expected time O n log n . This bound is shown to hold with high probability for a wide class of probability distributions on nonnegatively weighted Ž . digraphs. We also prove that