Shortest-Path Reconstruction Algorithms | Zendy

C.M. Khoong | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Shortest-Path Reconstruction Algorithms

Author(s) -

C.M. Khoong

Publication year - 1993

Publication title -

the computer journal

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.319

H-Index - 64

eISSN - 1460-2067

pISSN - 0010-4620

DOI - 10.1093/comjnl/36.6.588

Subject(s) - shortest path problem , distance , combinatorics , vertex (graph theory) , k shortest path routing , computer science , shortest path faster algorithm , path graph , distance matrix , path (computing) , floyd–warshall algorithm , algorithm , discrete mathematics , graph , mathematics , graph power , line graph , programming language

The shortest path problem in graphs is well known in computer science and operations research. This paper studies the problem of computing shortest paths between pairs of vertices in an n-vertex graph, given only the all pairs shortest paths distance matrix. This computation is called a reconstruction, since the algorithm has no access to explicit information about edges in the original graph. We present the following results: 1. A shortest path between a single pair of vertices can be reconstructed in O(n log n) time. 2. Shortest paths between all pairs of vertices can be reconstructed in O(n 3 ) time

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research