algorithmgraphdijkstravertices

Distance between every Vertices in Graph

Is there is an algo/efficient way to calculate the distance from each vertex in a graph to all other vertices.

Unlike Dijkstra - I'm looking for a way to calculate a distance for all vertices to all vertices (not one to all).

Thanks!

Solution

  • If by "distance" you mean "shortest distance", then the answer is "Yes". A very popular algorithm for all-pairs shortest paths is Floyd Warshall Algorithm. It is remarkably easy to implement:

    for k = 0 ; k != N ; k++
    for i = 0 ; i != N ; i++
        for j = 0 ; j != N ; j++
            W[i,j] = MIN(W[i,j], W[i,k]+W[k,j])

    It wouldn't work for large-scale sparse graphs, however, because it uses an adjacency matrix implementation. It also does not work with graphs that have negative cycles, because shortest paths in such graphs are undefined.