Dijkstra’s algorithm computes the shortest distance between two vertices in a graph. Vertices in a graph are connected by an edge with a positive length.
static int SingleSourceShortestPathForNonNegativeEdgeLength(Vertex v)
{
int min = short.MaxValue;
var crossingEdges = new MinHeap<short, short>(N);
var minVertices = new bool[N];
minVertices[v.Id - 1] = true;
foreach (var outgoingEdge in v.OutgoingEdges)
{
// Use a Heapify operation!
crossingEdges.Insert(outgoingEdge.V2, outgoingEdge.Length);
}
while (crossingEdges.Count > 0)
{
var minEdge = crossingEdges.ExtractMin();
short v2 = minEdge.Key;
var newVertex = vertices[v2 - 1];
minVertices[v2 - 1] = true;
if (minEdge.Value < min)
min = minEdge.Value;
foreach (var newEdge in newVertex.OutgoingEdges)
{
if (minVertices[newEdge.V2 - 1])
continue;
var edgeLength = (short)(newEdge.Length + minEdge.Value);
var edge = crossingEdges.Find(newEdge.V2);
if (edge!=null)
{
if (edgeLength < edge.Value)
crossingEdges.Update(newEdge.V2, edgeLength);
}
else
{
crossingEdges.Insert(newEdge.V2, edgeLength);
}
}
}
return min;
}
An extremely fast implementation for Heap which can be used in Dijkstra’s algorithm is shown below:
public class MinHeap<TKey, TValue>
where TValue : IComparable<TValue>
{
public class KeyValuePair
{
private TKey _key;
private TValue _value;
public KeyValuePair(TKey key, TValue value)
{
_key = key;
_value = value;
}
public TKey Key
{
get
{
return _key;
}
}
public TValue Value
{
get
{
return _value;
}
set
{
_value = value;
}
}
}
private KeyValuePair[] _heap;
private int _count = 0;
private Dictionary<TKey, int> _heapIndex;
private static readonly int BufferSize = 100;
public MinHeap()
{
_heap = new KeyValuePair[BufferSize];
_heapIndex = new Dictionary<TKey, int>(BufferSize);
}
public MinHeap(int capacity)
{
_heap = new KeyValuePair[capacity];
_heapIndex = new Dictionary<TKey, int>(capacity);
}
public int Count
{
get
{
return _count;
}
}
public void Insert(TKey key, TValue value)
{
var kvp = new KeyValuePair(key, value);
_heapIndex[key] = _count;
_heap[_count++] = kvp;
BubbleUp(_count - 1);
}
public void Delete(TKey key)
{
int nodeIndex = _heapIndex[key];
var kvp = _heap[--_count];
_heap[nodeIndex] = kvp;
_heapIndex[kvp.Key] = nodeIndex;
_heapIndex.Remove(key);
int parentIndex = GetParentIndex(nodeIndex);
bool bubbleUp = false;
if (parentIndex > 0)
{
var parentNode = _heap[parentIndex];
if (kvp.Value.CompareTo(parentNode.Value) < 0)
{
Swap(nodeIndex, parentIndex);
_heapIndex[key] = parentIndex;
_heapIndex[parentNode.Key] = nodeIndex;
BubbleUp(parentIndex);
bubbleUp = true;
}
}
if (!bubbleUp)
{
if (_count > (nodeIndex + 1))
{
BubbleDown(nodeIndex);
}
}
}
public KeyValuePair Find(TKey key)
{
if (_heapIndex.ContainsKey(key))
return _heap[_heapIndex[key]];
return null;
}
public void Update(TKey key, TValue value)
{
var nodeIndex = _heapIndex[key];
_heap[nodeIndex].Value = value;
int parentIndex = GetParentIndex(nodeIndex);
bool bubbleUp = false;
if (parentIndex >= 0)
{
var parentNode = _heap[parentIndex];
if (parentNode.Value.CompareTo(value) > 0)
{
Swap(nodeIndex, parentIndex);
_heapIndex[key] = parentIndex;
_heapIndex[parentNode.Key] = nodeIndex;
BubbleUp(parentIndex);
bubbleUp = true;
}
}
if (!bubbleUp)
{
int minIndex = GetMinChildIndex(nodeIndex);
if (minIndex > 0)
{
var minNode = _heap[minIndex];
if (value.CompareTo(minNode.Value) > 0)
{
Swap(nodeIndex, minIndex);
_heapIndex[key] = minIndex;
_heapIndex[minNode.Key] = nodeIndex;
BubbleDown(minIndex);
}
}
}
}
public KeyValuePair ExtractMin()
{
KeyValuePair min = _heap[0];
_count--;
if (_count > 0)
{
var kvp = _heap[_count];
_heap[0] = kvp;
TKey key = _heap[0].Key;
_heapIndex[key] = 0;
_heapIndex.Remove(min.Key);
if (_count > 1)
{
BubbleDown(0);
}
}
return min;
}
private void BubbleUp(int nodeIndex)
{
if (nodeIndex != 0)
{
int parentIndex = GetParentIndex(nodeIndex);
var node = _heap[nodeIndex];
var parentNode = _heap[parentIndex];
if (parentNode.Value.CompareTo(node.Value) > 0)
{
Swap(nodeIndex, parentIndex);
_heapIndex[node.Key] = parentIndex;
_heapIndex[parentNode.Key] = nodeIndex;
BubbleUp(parentIndex);
}
}
}
private void BubbleDown(int nodeIndex)
{
var node = _heap[nodeIndex];
int minIndex = GetMinChildIndex(nodeIndex);
if (minIndex > 0)
{
var minNode = _heap[minIndex];
if (node.Value.CompareTo(minNode.Value) > 0)
{
Swap(minIndex, nodeIndex);
_heapIndex[node.Key] = minIndex;
_heapIndex[minNode.Key] = nodeIndex;
BubbleDown(minIndex);
}
}
}
private void Swap(int node1, int node2)
{
var tmpNode = _heap[node1];
_heap[node1] = _heap[node2];
_heap[node2] = tmpNode;
}
private int GetParentIndex(int index)
{
return (index + 1) / 2 - 1;
}
private int GetChildStartIndex(int index)
{
return index * 2 + 1;
}
private int GetChildEndIndex(int index)
{
return index * 2 + 2;
}
private int GetMinChildIndex(int index)
{
int startIndex = GetChildStartIndex(index);
if (startIndex >= _count)
return -1;
int endIndex = GetChildEndIndex(index);
if (endIndex >= _count)
return startIndex;
return (_heap[startIndex].Value.CompareTo(_heap[endIndex].Value) < 0)
? startIndex : endIndex;
}
}
MinHeap implements two methods (at a minimum):
- Insert.
- Extract Min.
For Dijkstra’s algorithm, it is required to update the edge length from the middle of the heap. The above post has additional methods for a Min Heap to implement the update and delete operations.
Dijkstra’s algorithm is used to compute the All Pair Shortest Path problem (via the Johnson’s reweighting technique). Even for relatively dense graphs, Dijkstra’s algorithm is faster than the more general Floyd Warshall’s algorithm.
For a graph with 1000 vertices and 45,000 edges (m = n^1.63), the Floyd Warshall’s algorithm completed the computation in 6 seconds. Dijkstra’s algorithm computed in 3 seconds. For a graph with 20,000 vertices and nearly 1,000,000 edges (m = n^1.45), the Floyd Warshall’s algorithm computed in 7 hours, whereas Dijkstra’s algorithm computed under 20 minutes.
Clearly, Dijkstra’s algorithm with the Johnson reweights is a better solution than Floyd Warshall’s algorithm with a good Min Heap implementation.