DirectedGraph::allPairsShortestDistances

Function


void allPairsShortestDistances();

Calculate the Shortest Path between all pairs of vertices, save into the temp memory inside the Graph. Call the solution by function shortestPath()

Parameters

None

Return value

None

Example

#include "HKUAL_graph.h"
#include <iostream>
using namespace std;
using namespace HKUAL;

int main(){

    DirectedGraph<string> g;
    g.addVertex("A");
    g.addVertex("B");
    g.addVertex("C");
    g.addVertex("D");
    g.addEdge("A","B",4);
    g.addEdge("A","C", 10);
    g.addEdge("B","D", 7);
    g.addEdge("A","D", 3);
    g.allPairsShortestDistances();
    cout << g.shortestDistance("A","D") << endl;
    cout << g.shortestDistance("B","D") << endl;
    cout << g.shortestDistance("C","D") << endl;

    return 0;
}

Output

3
7
-1

Time Complexity

for is total number of vertices.

© The University of Hong Kong Algorithms Library - hkual@cs.hku.hk