.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.

Graph Traversal

In mathematics, a graph is a set of interconnected nodes. These nodes often represent real-world objects. For example, a graph may be used to represent a road network, with each node corresponding to a city, town, village or other place of interest. The connections between the nodes would represent the roads that join those places. A graph's connections may be symmetric or asymmetric, also known as undirected or directed respectively. A symmetric connection can be followed in both directions, such as most roads. An asymmetric connection can only be followed in one direction, perhaps representing a one-way street.

The diagram below shows an abstract representation of a graph. In this case we have eleven lettered nodes and seventeen connections. Four of the connections are asymmetric, shown with arrowheads denoting their direction. The other connections are undirected. One node, "Z", has no connections so cannot be reached from any of the others. The numbers indicate the distances between nodes.

Graph traversal algorithms, also known as graph search algorithms, follow the connections in graphs to solve specific problems. A common problem is finding the shortest route between two nodes. This is used in network routing protocols and satellite navigation systems for road users.

Dijkstra's algorithm, named after Edsger W Dijkstra, is a graph traversal algorithm. Given a starting point within a graph, the algorithm determines the shortest route to every other connected node. Unconnected nodes, such as "Z" in the diagram, are assigned a distance of infinity.