Algorithms. Dijkstra’s Algorithm. A Comprehensive Guide with Real-World Applications. Part 3.

In a previous article, I discussed the breadth-first search (BFS) algorithm. This algorithm can be used to find the shortest path between two nodes in an unweighted graph. If you're interested in learning more about algorithms, you might want to check out that article as well.

Dijkstra's algorithm is an extension of BFS and can handle graphs with weighted edges. It assigns tentative distance values to unvisited nodes and selects the node with the smallest tentative distance value. The algorithm examines all neighboring nodes, calculates the distance through the current node, and updates the tentative distance value if it is smaller. This process continues until the destination node is reached or all nodes are visited.

For more information on algorithms, including BFS, check out the book "Grokking Algorithms: An illustrated guide for programmers and other curious people" by Aditya Bhargava.

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path between two nodes in a graph. It was invented by Edsger W. Dijkstra in 1956 and is widely used in computer science and engineering. The algorithm assigns tentative distance values to unvisited nodes and selects the node with the smallest tentative distance value. It examines all neighboring nodes, calculates the distance through the current node, and updates the tentative distance value if it is smaller. This process continues until the destination node is reached or all nodes are visited.

Dijkstra's algorithm is efficient for sparse graphs and guarantees the shortest path when the graph has non-negative edge weights. For large graphs with many edges, more efficient algorithms such as A* may be used instead.

Implementation

Example

Suppose we have the following weighted directed graph, where the numbers on the edges represent their weights:

We want to find the shortest path from node A to node F using Dijkstra's algorithm. Here are the steps:

1. Initialization: Assign a tentative distance value of 0 to node A and infinity to all other nodes. Mark all nodes as unvisited. Set the current node to A.

2. Evaluate neighbors: For the current node A, evaluate all its neighbors and calculate their tentative distances from A. Update their tentative distances if they are smaller than the previous values.

3. Select next node: Select the unvisited node with the smallest tentative distance and mark it as visited. Set it as the current node.

4. Evaluate neighbors: For the current node B, evaluate all its neighbors and calculate their tentative distances from A. Update their tentative distances if they are smaller than the previous values.

5. Select next node: Select the unvisited node with the smallest tentative distance and mark it as visited. Set it as the current node.

6. Evaluate neighbors: For the current node E, evaluate all its neighbors and calculate their tentative distances from A. Update their tentative distances if they are smaller than the previous values.

7. Select next node: Select the unvisited node with the smallest tentative distance and mark it as visited. Set it as the current node.

8. Evaluate neighbors: For the current node C, evaluate all its neighbors and calculate their tentative distances from A. Update their tentative distances if they are smaller than the previous values.

9. The algorithm is finished. The shortest path from A to F is A -> E -> F with a total distance of 4.

Real-World Applications

1. Route planning: It determines the shortest path between two points based on distance, time, or cost in transportation systems.
2. Network routing: It finds the shortest path between two routers in a network, minimizing delay and congestion.
3. Genetics, bioinformatics, and social network analysis: It identifies the shortest evolutionary path between two species based on genetics, and the shortest path between two people based on connections. It helps to understand genetic relationships and identify influential individuals and groups.

Conclusion

This article covers Dijkstra's algorithm, which can handle graphs with weighted edges and is an extension of the breadth-first search algorithm. It assigns tentative distance values to unvisited nodes and selects the node with the smallest tentative distance value, updating the tentative distance value if it is smaller. This process continues until the destination node is reached or all nodes are visited. I also provide a Python implementation and an example of using it to find the shortest path between two nodes in a graph.

Dijkstra's algorithm is used in computer science and engineering, including route planning, network routing, genetics, bioinformatics, and social network analysis. It is efficient for sparse graphs and guarantees the shortest path with non-negative edge weights. For large graphs with many edges, more efficient algorithms such as A* may be used. To learn more about algorithms, I recommend the book "Grokking Algorithms" by Aditya Bhargava.