.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