Function
double shortestDistance(const T& x, const T& y);
Get the distance between two specified vertices.
Parameters
x, y are label of specified vertices.
Return value
Return shortest distance between two vertices.
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");
g.addEdge("A","C");
g.addEdge("B","D");
cout << g.shortestDistance("C","D") << endl;
DirectedGraph<string> g2;
g2.addVertex("A");
g2.addVertex("B");
g2.addVertex("C");
g2.addVertex("D");
g2.addEdge("A","B",4);
g2.addEdge("A","C", 10);
g2.addEdge("B","D", 7);
g2.addEdge("A","D", 3);
g2.addEdge("C","A", 20);
cout << g2.shortestDistance("C","D") << endl;
return 0;
} |
Output
Time Complexity
, for allPairShortestDistances() was excuted and no change on the graph structure.
, for the weight of all edges are 1, is number of edges and is total number of vertices.
, for the weight of edges are different, is number of edges and is total number of vertices. |