Dijkstra's algorithm

Dijkstras_progress_animation

DijkstraDemo

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

Overview

Dijkstra's algorithm is used to find the shortest path from a starting node (source) to a target node in a weighted graph. The graph can be directed or undirected, but the weights on the edges must be non-negative. The algorithm works by iteratively selecting the node with the smallest tentative distance, updating the distances of its adjacent nodes, and marking the selected node as "visited."

Algorithm Description

The algorithm maintains a set of nodes whose shortest distance from the source is known and a set of nodes whose shortest distance is not yet known. Initially, the distance to the source node is set to zero, and the distance to all other nodes is set to infinity. The algorithm proceeds as follows:

1. Initialize the distance to the source node to 0 and all other nodes to infinity.
2. Set the source node as the current node.
3. For the current node, consider all of its unvisited neighbors and calculate their tentative distances through the current node. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one.
4. After considering all of the unvisited neighbors of the current node, mark the current node as visited. A visited node will not be checked again.
5. If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity (when there is no connection between the source and remaining unvisited nodes), then stop. The algorithm has finished.
6. Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new "current node," and go back to step 3.

Pseudocode

The following is a high-level pseudocode description of Dijkstra's algorithm:

``` function Dijkstra(Graph, source):

 dist[source] ← 0
 for each vertex v in Graph:
   if v ≠ source:
     dist[v] ← infinity
   add v to Q
 while Q is not empty:
   u ← vertex in Q with min dist[u]
   remove u from Q
   for each neighbor v of u:
     alt ← dist[u] + length(u, v)
     if alt < dist[v]:
       dist[v] ← alt
       prev[v] ← u
 return dist, prev

```

Applications

Dijkstra's algorithm is widely used in network routing protocols, such as Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS). It is also used in various applications like geographic information systems (GIS) for finding the shortest path between locations on a map.

Limitations

While Dijkstra's algorithm is efficient for graphs with non-negative weights, it does not work correctly with graphs that contain negative weight edges. For such graphs, algorithms like the Bellman-Ford algorithm are used.

Related Pages

• Graph theory
• Shortest path problem
• Bellman-Ford algorithm
• A* search algorithm
• Edsger W. Dijkstra

See Also

• Floyd-Warshall algorithm
• Prim's algorithm
• Kruskal's algorithm