Dijkstra’s algorithm is a popular method used to find the shortest path between two nodes in a graph. Here is a general step-by-step procedure on how this algorithm works:
1. Initialization: Start at the node at which you are starting (call it the initial node). Set its ‘distance‘ to zero and set the ‘distance‘ for all other nodes to infinity.
2. Examine unvisited nodes: Visit all the unvisited neighbors of the current node. Calculate their tentative distance from the starting point through the current node. Compare the newly calculated tentative distance with the current assigned value and assign the smaller one.
3. Mark node as visited: After considering all of the unvisited neighbors of the current node, mark the current node as ‘visited‘. Visited nodes are not checked again.
4. Select next node: Out of the unvisited nodes, choose the node with the smallest tentative distance (priority queue can be used for this), set that as the current node, and go back to step 2.
5. Stop: If the destination node has been marked as visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity (no connection between initial and remaining unvisited nodes), stop the algorithm.
In mathematical terms:
Let G = (V, E) with non-negative edge weights w : E → R. Let d(v) denote the length of a shortest path from a vertex s to vertex v.
The Dijkstra’s Algorithm operates as follows:
1. **Initialization:**
s is the source vertex. Distances to all vertices are set to
+
d(s) = 0
+
d(v) = ∞
for all v ≠ s
2. All vertices are marked as unvisited and are inserted into a priority queue
3. Until the queue is empty, a vertex u with the smallest distance value is selected from the queue and its unvisited adjacent vertices are relaxed as follows:
+
if d(u) + w(u, v) < d(v)
+
then d(v) is updated to d(u) + w(u, v)
+ and new parent of v is set to u.
+ Then, u is marked as visited.
4. The algorithm concludes when the queue is empty.
Dijkstra’s algorithm typically uses a priority queue to select the vertex with minimum distance more quickly. It’s the basis of many routing protocols in modern systems, whether finding the optimal route between two locations on a map or routing packets over the internet.
Note that Dijkstra’s algorithm assumes that all edge weights are non-negative, as it greedily selects the smallest edge at each step.