Dijkstra’s Shortest Path Algorithm

First Page
Next Page

Dijkstra’s Shortest Path Algorithm

Dijkstra's algorithm is a widely used algorithm in graph theory and computer science, named after its inventor, Edsger W. Dijkstra. It is used to find the shortest path between two vertices in a weighted graph.

The algorithm works by maintaining a set of vertices for which the shortest path has already been determined. It begins at a starting vertex and iteratively explores its neighboring vertices, updating the shortest path to each neighbor as it progresses. The algorithm continues until it reaches the destination vertex or until all reachable vertices have been visited.

Here are the steps involved in Dijkstra's shortest path algorithm −

  • Initialize the algorithm by setting the starting vertex and assign it a distance of 0. Set the distance of all other vertices to infinity.

  • Select the vertex with the smallest distance that has not been visited yet. This vertex will be the current vertex.

  • Visit all the neighbors of the current vertex. For each neighbor, calculate the distance from the starting vertex through the current vertex. If this distance is shorter than the previously recorded distance for the neighbor, update the neighbor's distance.

  • Mark the current vertex as visited, meaning the shortest path to it has been determined.

  • Repeat steps 2 to 4 until the destination vertex is reached or until all vertices have been visited.

  • Once the destination vertex is reached or all vertices have been visited, the algorithm terminates. The shortest path from the starting vertex to the destination vertex can be obtained by backtracking from the destination vertex using the recorded shortest distances.

Dijkstra's algorithm guarantees to find the shortest path in a weighted graph, given that the graph does not contain negative edge weights. If negative edge weights are present, a different algorithm like Bellman-Ford should be used. Dijkstra's algorithm has various applications, including route planning in transportation networks, network routing protocols, and resource allocation in computer networks.

Certainly! Let's dive deeper into Dijkstra's algorithm and illustrate it with an example.

Consider the following weighted directed graph:

         4        2
   (A)------>(B)------>(C)
    |         | \       | \
    |         |  \      |  \3
   2|         |5  \2    |5  \
    |         |     \   |     \
    v         v      \  v      v
   (D)------>(E)----->(F)----->(G)
        3          1       5

Each vertex is labeled with a letter, and the numbers on the edges represent their weights or distances. We want to find the shortest path from vertex A to vertex G using Dijkstra's algorithm.

Step 1 - Initialize the algorithm by setting the starting vertex (A) and assign it a distance of 0. Set the distance of all other vertices to infinity.

Distance:
A: 0
B: ∞
C: ∞
D: ∞
E: ∞
F: ∞
G: ∞

Step 2: Select the vertex with the smallest distance that has not been visited yet. In this case, it's vertex A.

Step 3: Visit all the neighbors of the current vertex (A). Calculate the distance from the starting vertex (A) through the current vertex (A) to each neighbor. If this distance is shorter than the previously recorded distance for the neighbor, update the neighbor's distance.

Distance:
A: 0
B: 4 (via A)
C: ∞
D: 2 (via A)
E: ∞
F: ∞
G: ∞

Step 4: Mark the current vertex (A) as visited.

Step 5: Repeat steps 2 to 4 until the destination vertex (G) is reached or until all vertices have been visited.

Next, we select the vertex with the smallest distance that has not been visited, which is vertex D.

Distance:
A: 0
B: 4 (via A)
C: ∞
D: 2 (via A)
E: 5 (via D)
F: ∞
G: ∞

Now we mark vertex D as visited.

Next, we select vertex B, which has the smallest distance among the unvisited vertices.

Distance:
A: 0
B: 4 (via A)
C: 6 (via B)
D: 2 (via A)
E: 5 (via D)
F: ∞
G: ∞

After marking vertex B as visited, we proceed to vertex E.

Distance:
A: 0
B: 4 (via A)
C: 6 (via B)
D: 2 (via A)
E: 5 (via D)
F: 6 (via E)
G: ∞

Then, we visit vertex C.

Distance:
A: 0
B: 4 (via A)
C: 6 (via B)
D: 2 (via A)
E: 5 (via D)
F: 6 (via E)
G: 9 (via C)

Next, we visit vertex F.

Distance:
A: 0
B: 4 (via A)
C: 6 (via B)
D: 2 (via A)
E: 5 (via D)
F: 6 (via E)
G: 9 (via C or F)

Finally, we visit vertex G.

Distance:
A: 0
B: 4 (via A)
C: 6 (via B)
D: 2 (via A)
E: 5 (via D)
F: 6 (via E)
G: 9 (via C or F or G)

Step 6: Once the destination vertex (G) is reached or all vertices have been visited, the algorithm terminates. The shortest path from vertex A to vertex G can be obtained by backtracking from the destination vertex using the recorded shortest distances.

In this case, the shortest path from A to G is A -> D -> E -> F -> G with a total distance of 9.

That's how Dijkstra's algorithm works! It iteratively explores the graph, updating the distances to find the shortest path from the starting vertex to all other vertices.

First Page
Next Page