Section 3 - The Dijkstra Implementation
10B.3.1 Preparatory Discussion for Implementation
We are ready to implement. Our first choice is whether or not to implement Dijkstra within the FHgraph template or external to it. Since you will have occasion to do both, I will show you an internal implementation for Dijkstra, today, and an external for Kruskal, our topic for next time. You will then have a prototype of both approaches for future development.
To implement Dijkstra, we have to make sure our FHvertex is capable of providing the needed numeric data, namely distance to S. Of course, I made sure that it was by supplying a dist member, a numeric value, which can be int, float, or whatever the client is using for its cost information. In addition, I added an FHvertex* member nextInPath that will help us know the actual shortest path. Here is a reminder of the FHvertex data where these two members appear:
EdgePairList adjList; Object data; CostType dist; VertPtr nextInPath; // used for client-specific info
Because dist and nextInPath are strictly reliant on the vertex from which we are measuring all shortest paths, S, they are volatile and will only be relevant to the current and/or most recent application of dijkstra. Therefore, one has to be aware that this data can get stale very fast. Either we need to use it immediately after applying dijkstra, which will presumably leave the "answers" in those members, or we must actually invoke the dijkstra algorithm explicitly from within any other method that expects fresh values there. For now, we merely note that our algorithm will use and modify the values in dist and nextInPath as it progresses, and those members will contain their correct, terminal values when the algorithm ends.
Finally, we had better be clear about what kind of graph dijkstra applies to:
- Dijkstra applies to graphs with positive edge costs.
- It works for both directed and undirected graphs.
- The graph does not have to be "connected", that is, it's okay if you cannot get to every vertex from every other vertex. Those vertices which are unreachable will have their final path distances = infinity, which is correct.
- Non-directed graphs will yield correct results only if each edge, (v, w), is represented twice in the adjacency table: once from v to w and once from w to v. Both costs should be equal.
10B.3.2 Implementation
We've already discussed the algorithm and implementation aspects in great detail, so I will present the implementation here with very little commentary. The preparation was tailor-made for this precise implementation, making the correspondence very tight between the two.
template <class Object, typename CostType>
bool FHgraph<Object, CostType>::dijkstra(const Object & x)
{
typename VertPtrSet::iterator vIter;
typename EdgePairList::iterator edgePrIter;
VertPtr wPtr, sPtr, vPtr;
CostType vostVW;
queue<VertPtr> partiallyProcessedVerts;
sPtr = getVertexWithThisData(x);
if (sPtr == NULL)
return false;
// initialize the vertex list and place the starting vert in p_p_v queue
for (vIter = vertPtrSet.begin(); vIter != vertPtrSet.end(); ++vIter)
(*vIter)->dist = Vertex::INFINITY;
sPtr->dist = 0;
partiallyProcessedVerts.push( sPtr ); // or, FHbinHeap::insert(), e.g.
// outer dijkstra loop
while( !partiallyProcessedVerts.empty() )
{
vPtr = partiallyProcessedVerts.front();
partiallyProcessedVerts.pop();
// inner dijkstra loop: for each vert adj to v, lower its dist to s if you can
for (edgePrIter = vPtr->adjList.begin();
edgePrIter != vPtr->adjList.end();
edgePrIter++)
{
wPtr = edgePrIter->first;
vostVW = edgePrIter->second;
if ( vPtr->dist + vostVW < wPtr->dist )
{
wPtr->dist = vPtr->dist + vostVW;
wPtr->nextInPath = vPtr;
// *wPtr now has improved distance, so add wPtr to p_p_v queue
partiallyProcessedVerts.push(wPtr);
}
}
}
return true;
}
The comments explain exactly what aspect of the algorithm they implement, however there is one statement that does not correspond to our previous discussion:
wPtr->nextInPath = vPtr;
This is the line that allows us to track the actual path from S to each vertex in question. However, this way of linking results in a path that is pointing back from each destination vertex toward the origin, S, rather than from S to each destination vertex. You will see how we reverse this ad-hoc singly linked list.
There is one helper method that needs to be defined for the above algorithm to work. It takes some data, x, and returns the vertex object in the graph's master vertexSet that contains that data. Here it is:
template <class Object, typename CostType>
FHvertex<Object, CostType>* FHgraph<Object, CostType>::getVertexWithThisData(
const Object & x)
{
typename VertexSet::iterator findResult;
Vertex vert(x);
Vertex::pushSortKey(); // save client sort key
Vertex::setSortType(Vertex::SORT_BY_DATA);
findResult = vertexSet.find(vert);
Vertex::popSortKey(); // restore client value
if ( findResult == vertexSet.end() )
return NULL;
return (VertPtr)&*findResult; // the address of the vertex in the set of originals
}
10B.3.3 Reporting Methods
We next need methods to report results. One will print a full table of path-length results for the specified origin vertex, S. The other will show the shortest path between S and any other vertex.
The method that prints out the full table of path lengths is very short:
// applies dijkstra, prints all distances - could be modified to skip dijkstra
template <class Object, typename CostType>
bool FHgraph<Object, CostType>::showDistancesTo(const Object & x)
{
typename VertPtrSet::iterator vIter;
if (!dijkstra(x))
return false;
cout << "Dist to " << x << " ----------- \n";
for (vIter = vertPtrSet.begin(); vIter != vertPtrSet.end(); ++vIter)
{
cout << (*vIter)->data << " " << (*vIter)->dist << endl;
}
return true;
}
There is an extremely elegant and short implementation of a function that prints out the shortest path after dijkstra has been applied as above. It uses recursion nicely. You can find that in the text or other sources, but I will present a nice alternative since it uses a stack -- the prefect solution to reverse a list.
// applies dijkstra, prints shortest path - could be modified to skip dijkstra
template <class Object, typename CostType>
bool FHgraph<Object, CostType>::showShortestPath(const Object & x1,
const Object & x2)
{
VertPtr vp, start, stop;
stack<VertPtr> pathStack;
start = getVertexWithThisData(x1);
stop = getVertexWithThisData(x2);
if (start == NULL || stop == NULL)
return false;
// perhaps add argument indicating choice to skip this if pre-computed
dijkstra(x1);
for (vp = stop; vp != start; vp = vp->nextInPath)
pathStack.push(vp);
pathStack.push(vp);
cout << "Cost of shortest path from " << x1 << " to " << x2 << ": "
<< stop->dist << endl;
while (true)
{
vp = pathStack.top();
pathStack.pop();
if ( pathStack.empty() )
{
cout << vp->data << endl;
break;
}
cout << vp->data << " --> ";
}
return true;
}
10B.3.4 The Test Client
We finish this week by showing a client and its output:
// FHgraph and djikstra algorithm
// CS 2C Foothill College
#include <iostream>
#include <string>
using namespace std;
#include "FHgraph.h"
// string is the data of the vertex; int is the cost type of edges
// --------------- main ---------------
int main()
{
// build graph
FHgraph<string, int> myGraph1;
myGraph1.addEdge("v1","v2", 2); myGraph1.addEdge("v1","v4", 1);
myGraph1.addEdge("v2","v4", 3); myGraph1.addEdge("v2","v5", 10);
myGraph1.addEdge("v3","v1", 4); myGraph1.addEdge("v3","v6", 5);
myGraph1.addEdge("v4","v3", 2); myGraph1.addEdge("v4","v5", 2);
myGraph1.addEdge("v4","v6", 8); myGraph1.addEdge("v4","v7", 4);
myGraph1.addEdge("v5","v7", 6);
myGraph1.addEdge("v7","v6", 1);
// for debugging - only works if cout << overloaded for data type
myGraph1.showAdjTable();
// dijkstra called from inside
myGraph1.showDistancesTo("v2");
cout << endl;
myGraph1.showShortestPath("v2", "v3");
myGraph1.showShortestPath("v2", "v6");
myGraph1.showShortestPath("v2", "v7");
cout << endl;
return 0;
}The run:
------------------------ Adj List for v1: v2(2) v4(1) Adj List for v2: v4(3) v5(10) Adj List for v4: v5(2) v3(2) v6(8) v7(4) Adj List for v5: v7(6) Adj List for v3: v1(4) v6(5) Adj List for v6: Adj List for v7: v6(1) Dist to v2 ----------- v1 9 v2 0 v4 3 v5 5 v3 5 v6 8 v7 7 Cost of shortest path from v2 to v3: 5 v2 --> v4 --> v3 Cost of shortest path from v2 to v6: 8 v2 --> v4 --> v7 --> v6 Cost of shortest path from v2 to v7: 7 v2 --> v4 --> v7
This lesson -- the description and implementation of a shortest path algorithm -- represents the culmination of what you have been doing in this course: using C++ and its STL templates to solve a classic problem in data structure theory. In the process you understood that you could have used your own ADTs rather than STL's. We also provided back-of-the-envelope proofs of the correctness of the algorithm and weighed pros-and-cons of different choices we might have made. If you want to focus your attention on three pages that embody your understanding of the material of this course, you should reread and compile everything in these last three pages until you are an expert. You can also make a copy of FHgraph.h and change it to use our recently home-spun ADTs in preference to the STL versions. Also, try different graphs and data types to reinforce the client use of the algorithm. That's how you get your money's worth out of your Foothill College tuition.
Next time we will take on one of the other major algorithms in graph theory, the MST, or Minimum Spanning Tree, algorithm, which. like the Shortest Path Problem, has countless applications in technology, business and science.