Shortest Path

Shortest path: Dijkstra's algorithm

The shortest path algorithm is a graph theory algorithm that helps to find the shortest path between two nodes in a weighted graph (usually between the specified source and destination nodes). A weighted graph is a graph where each edge connecting two nodes has a numerical value assigned to it, called a weight. The weight typically represents the cost, distance, or time associated with traversing that edge. The shortest path between two nodes is the path with the lowest sum of edge weights.

There are several algorithms to find the shortest path, with Dijkstra's algorithm and the Bellman-Ford algorithm being two well-known examples. Here, we will use Dijkstra's algorithm to illustrate the concept. Let’s start with the algorithm:

1. First, it assigns a tentative distance value to every vertex (node) in the graph: 0 for the starting vertex and infinity for all other vertices.

2. Then it sets the starting vertex as the current vertex and marks it as visited.

3. For each neighbor of the current vertex, it calculates the distance to the neighbor through the current vertex. If this distance is less than the neighbor's current tentative distance, update the tentative distance.

4. After, it selects the unvisited vertex with the lowest tentative distance as the new current vertex and marks it as visited.

5. Finally, it repeats steps 3–4 until all vertices are visited or the target vertex is visited.

Implementing the algorithm in Python

Consider a simple graph with five nodes (A, B, C, D, E) and the following edges with weights: