  The Floyd-Warshall algorithm is the most popular algorithm for determining
the shortest paths between all pairs in a graph. It is very a simple and an
elegant algorithm. However, if the graph does not contain any negative weighted
edge, using Dijkstra's shortest path algorithm for every vertex as a source
vertex to produce all pairs shortest paths of the graph works much better than
the Floyd-Warshall algorithm for sparse graphs. Also, for the graphs with
negative weighted edges, with no negative cycle, Johnson's algorithm still
performs significantly better than the Floyd-Warshall algorithm for sparse
graphs. Johnson's algorithm transforms the graph into a non-negative one by
using the Bellman-Ford algorithm, then, applies the Dijkstra's algorithm. Thus,
in general the Floyd-Warshall algorithm becomes very inefficient especially for
sparse graphs. In this paper, we show a simple improvement on the
Floyd-Warshall algorithm that will increases its performance especially for the
sparse graphs, so it can be used instead of more complicated alternatives.
