Warnock Inc. Technology Consultation for the Future

Now that we have a table of intersections and a table of links, we are ready to calculate the shortest or fastest route. To do this, we will use a graph. In mathematics, a graph is not just an image w/ lines or a pie chart; a graph is a mathematical representation of nodes (points) and edges (lines). This is equivalent to our intersections and streets, or links. To calculate the fastest or shortest path, we must know how the points connect to each other, and what their weight is. The weight can be the time it takes to get to a point, or the distance from point to point depending on the type of calculation. Wikipedia has a good article on graph theory.

Once we have the data in a graph, we must find the correct path. This is done by using a shortest path algorithm. A shortest path algorithm takes these nodes and edges and returns the path from the starting node to the ending node. An example of shortest path algorithm is internet routing. A packet takes the shortest path to get from the source to destination on the internet.

Dijkstra's Algorithm
Dijkstra's Algorithm is a common algorithm that searches all edges to find the shortest path not only to the end, but to all nodes in the graph. Again, Wikipedia has a great article and explanation of Dijkstra's Algorithm.

Code
I have seen a few code examples that utilize Dijkstra's Algorithm, but the best example I have found so far was created by http://www.4guysfromrolla.com/. The project can be downloaded here, and has several projects in it. The project skmDataStructures contains datatypes for graphs, nodes and edges as well as methods to add the edges and nodes to a graph. The Solution also contains a project GraphTester that has an example of how Dijkstra's works by have a set of cities in California, and how the cities are connected by flights.

This is a quick run through of the code. A graph is created called SoCalMap. The nodes & edges for each city are added to the graph:

// add the nodes to the graph, if needed
if (!SoCalMap.Contains(city1))
SoCalMap.AddNode(new Node(city1, null));
if (!SoCalMap.Contains(city2))
SoCalMap.AddNode(new Node(city2, null));
SoCalMap.AddUndirectedEdge(city1, city2, distance);

There are two hash tables that store the route and the distances to each point. The hashtable is made up of keys that are the cities, and the value is the distance. All values in dist are made to be infinity (or Int32.MaxValue). All values of route are set to null. As the algorithm calculates the route, these values populate. The initial distance, or the distance from the start to start (itself), is obviously zero.

foreach(Node n in SoCalMap.Nodes)
{
dist.Add(n.Key, Int32.MaxValue);
route.Add(n.Key, null);
}

// set the initial distance of start to 0
dist[start] = 0;

The actual calculation is done here:

/**** START DIJKSTRA ****/
while (nodes.Count > 0)
{
Node u = GetMin(nodes); // get the minimum node
nodes.Remove(u); // remove it from the set Q

// iterate through all of u's neighbors
foreach(EdgeToNeighbor edge in u.Neighbors)
Relax(u, edge.Neighbor, edge.Cost); // relax each edge
} // repeat until Q is empty
/**** END DIJKSTRA ****/

It is a loop that runs until all nodes have been exhausted. GetMin finds the next hop by finding the hop with the shortest distance from the start node. Next the edges of the neighbors of this nodes neighbors are relaxed (which means that dist and route are updated. In the end, you have dist and route. Starting with route[end], you find the next hope; follow this node until route[x] = start, and that is the path. dist[x] for each hop is added together to get the total distance (or time if thats what we are using).

Using it with our data

For this application, we are using the skmDataStructures project, and some of the code in the GraphTester. We will get our data from SQL.

we will load our data with:

// get values from sql
String intersectionId1 = myReader["intersectionId1"].ToString();
String intersectionId2 = myReader["intersectionId2"].ToString();
int time = (int)myReader["time"];

// add values to nodes
if (!virginia.Contains(intersectionId1))
virginia.AddNode(new Node(intersectionId1, null));
if ( !virginia.Contains(intersectionId2))
virginia.AddNode(new Node(intersectionId2, null));
virginia.AddUndirectedEdge(intersectionId1, intersectionId2, time);

Just like in the example project, we initialize our dist and route with:

InitDistRouteTables(start, ref Dist, ref Route); // initialize the route & distance tables

However, since we have tens of thousands of intersections, we can't list them all in a listbox, we should pick a few intersections around the county. Search the TIGER_01 table for a road, and use it's from or two lat/long to find the intersectionID. I have a few points around the county, some close and some far away to test the processing time. Lastly, I optimized the algorithm to end when the end point is found. By definition, Dijkstra's runs until the shortest path to all nodes is found. This stops the process much earlier. The code that I'm using can be found here.

Results
This method works well. It is very accurate. Open the c:\route.csv file and graph the path in Microsoft Streets & Trips or Map Point and you will see the results are what you'd expect, like using highways instead of local streets. The only problem with this method is, is that it can be painfully slow. A route that is a few blocks away takes 2 seconds, but a destination that is 5 miles away can take 2 minutes to calculate. Trips across the county can take 10 or 20 minutes to calculate.