BlackWaspTM

This web site uses cookies. By using the site you accept the cookie policy.This message is for compliance with the UK ICO law.

Algorithms and Data Structures
.NET 3.5+

Dijkstra's Algorithm

Graph traversal algorithms are used to process a graph of interconnected nodes, visiting each node by following a set behaviour. Dijkstra's algorithm is such an algorithm. It determines the shortest path from a start point to all other nodes in a graph.

Testing the Calculator

We can test the algorithm by creating a graph and traversing it. The code below creates the graph pictured at the start of this article. The distances from the "G" node are calculated and the results outputted. Try changing the distances or the starting point and viewing the results.

Graph graph = new Graph();

//Nodes
graph.AddNode("A");
graph.AddNode("B");
graph.AddNode("C");
graph.AddNode("D");
graph.AddNode("E");
graph.AddNode("F");
graph.AddNode("G");
graph.AddNode("H");
graph.AddNode("I");
graph.AddNode("J");
graph.AddNode("Z");

//Connections
graph.AddConnection("A", "B", 14, true);
graph.AddConnection("A", "C", 10, true);
graph.AddConnection("A", "D", 14, true);
graph.AddConnection("A", "E", 21, true);
graph.AddConnection("B", "C", 9, true);
graph.AddConnection("B", "E", 10, true);
graph.AddConnection("B", "F", 14, true);
graph.AddConnection("C", "D", 9, false);
graph.AddConnection("D", "G", 10, false);
graph.AddConnection("E", "H", 11, true);
graph.AddConnection("F", "C", 10, false);
graph.AddConnection("F", "H", 10, true);
graph.AddConnection("F", "I", 9, true);
graph.AddConnection("G", "F", 8, false);
graph.AddConnection("G", "I", 9, true);
graph.AddConnection("H", "J", 9, true);
graph.AddConnection("I", "J", 10, true);

var calculator = new DistanceCalculator();
var distances = calculator.CalculateDistances(graph, "G");  // Start from "G"

foreach (var d in distances)
{
    Console.WriteLine("{0}, {1}", d.Key, d.Value);
}

/* OUTPUT

A, 28
B, 22
C, 18
D, 27
E, 29
F, 8
G, 0
H, 18
I, 9
J, 19
Z, Infinity

*/
29 May 2011