Shortest Path Algorithm - QuickGraph - Chad Brooks Web Log - Site Home

I happend across an interesting problem the other day. How do you code a shortest path algorithm? Actually, this happened to cross over very well to one of my other main interests - gaming. Doing some research on gamedev.net, I happened across a really great library called QuickGraph. It is based upon the Boost Graph Library.

Well, that is all good - except for the fact that the documentation is really poor. Especially for someone who has no idea about Dijkstra's and BellmanFord's. Well, this will be my attempt to explain my problem and how I solved it with QuickGraph.

The Problem: Calculate the shortest route between solar systems in a very popular MMRPG.

The Solution: Use the BreadthFirstSearchAlgorithm in the QuickGraph Library. This algorithm assumes equal distance between all points and will check all surrounding points from the start in "Waves". The key to measuring distance is checking those waves and incrementing distance from the predecessor. This is done using a "visitor" pattern which is built using the RecordPredecessor delegate. Please feel free to comment if I need to clear this up.

A bit of pseudocode:

{

// Set up the graph
private AdjacencyGraph g = new AdjacencyGraph(
   new VertexAndEdgeProvider(), // vertex and edge provider
   true); // directed graph
   //Add Vertices
   IVertex x = g.AddVertex();
   // Add Edges (path between the stars)
   IEdge y = g.AddEdge(a,b);
   BreadthFirstSearchAlgorithm bfs = new BreadthFirstSearchAlgorithm(g);
   // adding handlers
   bfs.TreeEdge += new EdgeHandler( RecordPredecessor );
     bfs.InitializeVertex += new VertexHandler( InitializeVertex );

// Now compute the graph
bfs.Compute((IVertex)htReverse[startID.ToString()]);

}

private void InitializeVertex(object o, VertexEventArgs v)

{
m_Distances[v.Vertex] = 0;
}

// This happens each time a "Wave" occurs
// Acutally, this happens upon every vertex hit, but it should only record 1 per "wave"
private void RecordPredecessor(object sender, EdgeEventArgs args)
{
   m_Distances[args.Edge.Target] = m_Distances[args.Edge.Source] + 1;
   IVertex z = args.Edge.Source;
   if (htForward[z].ToString() == m_end.ToString())
   {
      // Remember that we have to remove one, as the graph program is counting vertices and not jumps
      Distance = m_Distances[args.Edge.Target] - 1;
   }

}