Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6884638 | Journal of Network and Computer Applications | 2018 | 16 Pages |
Abstract
We describe a new forward-backward method for an all-pairs shortest-paths (APSP) algorithm. While most APSP algorithms only scan edges forward, the algorithm proposed here also scans all edges backward because it assumes that edges in the outgoing and incoming adjacency lists of the vertices appear with the same importance. The running time of the algorithm on a directed graph with n vertices, and m edges and positive real-valued edge weights in a deterministic way is O(nδ2â2logδ(nâ1)â1â), and the space complexity is O(nδâ2logδ(nâ1)â1â), where δâ¯=â¯mân is the density of the graph. Simulations on graphs with up to 10000 vertices with real, positive weights show that our FB-APSP algorithm, using additional working space less than 75% of space used by Speed-Up Floyd-Warshall algorithm, is faster on large sparse graphs, particularly planar graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Networks and Communications
Authors
Dyson Pereira Junior, Emilio Carlos Gomes Wille,