Warnock Inc. Technology Consultation for the Future

Because when using Dijkstra's Algorithm as-is, the processing time is pretty high when calculating routes with our current code, we need to optimize the process. The first optimization we did was to end the processing when the end point is found. I ran some tests on the code and the GetMin() function was taking the longest time. This function loops through all existing nodes to find the shortest distance to the next node. We can optimize this if we keep these nodes in order using a Priority Queue.

For this task, I took the existing dist type, which is a hashtable, and modified it to keep track of the keys and put them in order. hashtable uses and object for a key and for the value. For our purposes, i forced the key to be a string, and the value to be an integer. This is essentially a hashtable with some "add-ons". This is the PriorityQueue class i'm using:

Code
public class PriorityQueue
{
#region Private Member Variables
// private member variables
private Hashtable list = new Hashtable(); // main object
private ArrayList keys = new ArrayList(); // list of keys so we can display in order
#endregion

#region Constructors
public PriorityQueue() { } // remove default constructor

#endregion

#region Public Methods
#region Add Methods
///
/// priority queue
///
protected internal virtual void Add(string key, int data)
{
list.Add(key, data);

if (keys.Count == 0)
{
keys.Add(key); // no keys, add first one
}
else
{ // existing keys, put in correct order.
for (int a = 0; a < keys.Count; a++)
{
if (data <= (int)list[keys[a]])
{
keys.Insert(a, key); // inserts the key into the list if the value is less than previous value
break;
}
}
}
}

protected internal virtual void Clear()
{
list.Clear();
}

protected internal virtual void Remove(string key)
{
keys.Remove(key);
}

protected internal virtual int this[string key]
{
get
{
return (int)list[key];
}
set
{
list[key] = value;
keys.Remove(key); // removes value since it is not in order
for (int a = 0; a < keys.Count; a++) // adds key back in order
{
if (value <= (int)list[keys[a]])
{
keys.Insert(a, key); // inserts the key into the list if the value is less than previous value
break;
}
}
}
}

#endregion
#endregion

#region Public Properties
///
/// Returns the number of values.
///
public virtual int Count
{
get
{
return list.Count;
}
}

public virtual string minimum
{
get
{
return (string)keys[0];
}
}

#endregion
}

The new GetMin()
this alters the way we use GetMin(). GetMin() is simplified to:

private Node GetMin(NodeList nodes, PriorityQueue dist, String end)
{
// find the node in nodes with the smallest distance value
return nodes[dist.minimum];
}

All references to Dist must be changed to PriorityQueue. Dist is defined as:

private PriorityQueue Dist = new PriorityQueue();

The new code can be found here.

Results
The route is found much faster using the priority queue. For all routes around the county, calculations take about 20 seconds. This is not perfect, but much faster than before.