Untitled Document

Function

void allPairsShortestPath();

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

Parameters

None

Return value

None

Example

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

int main(){

    Graph<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
13

Time Complexity

for is total number of vertices.

Graph::allPairsShortestPath

Parameters

Return value