The Floyd-Warshall all-pairs shortest paths algorithm for disconnected and very sparse graphs

Date

2023-01-01

Author

Toroslu, İsmail Hakkı

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

378
views

0
downloads

The Floyd-Warshall algorithm is the most popular algorithm for determining the shortest paths between all vertex pairs in a graph. It is a very simple and an elegant algorithm. However, for graphs without any negative weighted edges, using Dijkstra's shortest path algorithm for every vertex as a source vertex to produce all-pairs shortest paths works significantly better than the Floyd-Warshall algorithm, especially for large graphs. Furthermore, for graphs with negative weighted edges, with no negative cycle, in general Johnson's algorithm also performs better than the Floyd-Warshall algorithm for large graphs. Johnson's algorithm first transforms the graph into a non-negative one by using the Bellman-Ford algorithm, then applies the Dijkstra's algorithm to the transformed graph. Thus, mainly, the Floyd-Warshall algorithm is quite inefficient, especially for large graphs. In this paper, we show a simple improvement on the Floyd-Warshall algorithm that will increases its efficiency, especially for very sparse graphs (i.e., the number of its edges is less than the number of its vertices), so it can be used instead of more complicated alternatives. We also show that our approach is also very effective for denser disconnected graphs. Since the new algorithm modifies the original Floyd-Warshall algorithm, it is mainly aimed for directed graphs without negative cycles. Most programmers prefer to implement the Floyd-Warshall algorithm over more complicated but more efficient alternatives for solving all-pairs shortest path problems. In this work, we show that without the addition of any complicated data structures, the performance of the Floyd-Warshall algorithm can be improved very easily. Our practical approach works even better than its alternatives for large sparse graphs.

Subject Keywords

all-pairs shortest path problem, Dijkstra's algorithm, Floyd-Warshall algorithm, Johnson's algorithm, sparse graphs, all-pairs shortest path problem, Dijkstra's algorithm, Floyd-Warshall algorithm, Johnson's algorithm, sparse graphs

URI

https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85147452442&origin=inward
https://hdl.handle.net/11511/102441

Journal

Software - Practice and Experience

DOI

https://doi.org/10.1002/spe.3188

Collections

Department of Computer Engineering, Article

Suggestions

OpenMETU
Core

A Layout algorithm for visualization of graph alignments Akarsu, Andaç; Can, Tolga; Department of Computer Engineering (2017) Graph layout algorithms are commonly used when visualizing. Usually these algorithms focus on a single graph. To be able to visualize multiple graphs at once, such as the results of graph alignment algorithms on biological networks, new layout algorithms need to be developed. A layout algorithm for visualizing graph alignments should display the aligned graphs separately, so that both the graphs and their alignment can be viewed individually. In addition, for better interpretation of the alignment results, ...
Efficient Surface Integral Equation Methods for the Analysis of Complex Metamaterial Structures Yla-Oijala, Pasi; Ergül, Özgür Salih; Gurel, Levent; Taskinen, Matti (2009-03-27) Two approaches, the multilevel fast multipole algorithm with sparse approximate inverse preconditioner and the surface equivalence principle algorithm, are applied to analyze complex three-dimensional metamaterial structures. The efficiency and performance of these methods are studied and discussed.
The static stochastic knapsack problem with normally distributed item sizes Merzifonluoglu, Yasemin; Geunes, Joseph; Romeijn, H. Edwin (Springer Science and Business Media LLC, 2012-09-01) This paper develops exact and heuristic algorithms for a stochastic knapsack problem where items with random sizes may be assigned to a knapsack. An item's value is given by the realization of the product of a random unit revenue and the random item size. When the realization of the sum of selected item sizes exceeds the knapsack capacity, a penalty cost is incurred for each unit of overflow, while our model allows for a salvage value for each unit of capacity that remains unused. We seek to maximize the ex...
The Schur algorithm and reproducing kernel Hilbert spaces in the ball Alpay, D; Bolotnikov, V; Kaptanoglu, HT (Elsevier BV, 2002-02-15) Using reproducing kernel Hilbert spaces methods we develop a Schur-type algorithm for a subclass of the functions analytic and contractive in the ball. We also consider the Nevanlinna-Pick interpolation problem in that class. (C) 2002 Elsevier Science Inc. All rights reserved.
A Customized force-directed layout algorithm with genetic algorithm techniques for biological graphs whose vertices have enzyme commission attributes Aksoydan, Fırat; Atalay, Mehmet Volkan; Department of Computer Engineering (2019) A pathway can be visualized as a graph whose layout is drawn by a force-directed algorithm. In our previous study, we have described EClerize which is a customized and improved Kamada Kawai force-directed algorithm in order to visualize pathways that contain nodes with attributes as EC numbers. EClerize creates clusters of vertices with enzymes that belong to the same EC class. Here, we make use of genetic algorithm (GA) to obtain a global optimum solution for EClerize and we integrate undirected graph layo...

Citation Formats

İ. H. Toroslu, “The Floyd-Warshall all-pairs shortest paths algorithm for disconnected and very sparse graphs,” Software - Practice and Experience, pp. 0–0, 2023, Accessed: 00, 2023. [Online]. Available: https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85147452442&origin=inward.