DirectedGraph::shortestPath
Function
vector<Edge<T> >shortestPath(const T& x, const T& y);
Get the shortest path between two specified vertices.
Parameters
x, y are the labels of specified vertices.
Return value
Return a vector contains edges of shortest path between two vertices.
Example
#include "HKUAL_graph.h"
#include <iostream>
#include <vector>
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", 23);
vector<DirectedEdge<string> > v = g.shortestPath("A", "D");
for (int i = 0; i < v.size(); i++)
cout << v[i].X << ' ' << v[i].Y << endl;
return 0;
} |
Output
| A B B D |
Time Complexity
.gif){kind=small}
, for the weight of all edges are 1,
is number of edges and 
is total number of vertices..gif){kind=small}
, for the weight of edges are different, is number of edges and is total number of vertices.