Dijkstra’s Algorithm

Learn Dijkstra’s Algorithm, a greedy method for finding the single-source shortest path in weighted graphs. Understand step-by-step execution, time complexity, and real-world applications.

Dijkstra’s Algorithm

(Single Source Shortest Path)

Introduction

Dijkstra’s Algorithm is a well-known greedy algorithm used to find the shortest path from a source vertex to all other vertices in a weighted, directed, or undirected graph.

Properties:

• All edge weights must be non-negative.
• It returns the shortest path from a single source to all vertices.

Basic Idea

The main principle of Dijkstra’s Algorithm is:

• Always select the vertex with the shortest distance from the source and mark it as permanent.
• Then, update the distances of all its neighboring vertices.

By repeating this process, the shortest path from the source to all vertices is determined efficiently.

Steps of the Algorithm

1. Mark all vertices in two ways:
   • Permanent: Distance is fixed.
   • Temporary: Distance can still be updated.
2. Set the distance of the source vertex to 0 and all other vertices to infinity.
3. Update the distances of all neighbors connected to the current vertex:

distance[neighbor]=min⁡(distance[neighbor],distance[current]+weight(current,neighbor))distance[neighbor] = \min(distance[neighbor], distance[current] + weight(current, neighbor))distance[neighbor]=min(distance[neighbor],distance[current]+weight(current,neighbor))

1. Select the vertex with the smallest temporary distance and make it permanent.
2. Repeat steps 3–4 until all vertices are marked permanent.

Algorithm (Pseudo Code)

Dijkstra(Graph, source):

    for each vertex v:

        distance[v] = ∞

        visited[v] = false

    distance[source] = 0

    while there are unvisited vertices:

        u = vertex with minimum distance and not visited

        visited[u] = true

        for each neighbor v of u:

            if not visited[v]:

                distance[v] = min(distance[v], distance[u] + weight(u, v))

    return distance[]

Example

Graph edges and weights:

Source vertex: A

Step-by-step process:

1. Initialize distances: distance[A] = 0, distance[B,C,D,E] = ∞
2. Update neighbors of A:
   • distance[B] = 4
   • distance[C] = 2
3. Select C (smallest temporary) → permanent, update neighbors:
   • distance[B] = min(4, 2+1) = 3
   • distance[D] = 2+8 = 10
   • distance[E] = 2+10 = 12
4. Select B → permanent, update neighbors:
   • distance[D] = min(10, 3+5) = 8
5. Select D → permanent, update neighbors:
   • distance[E] = min(12, 8+2) = 10
6. Select E → permanent

Shortest distances from A:

• A = 0, B = 3, C = 2, D = 8, E = 10

Time Complexity

• Using adjacency matrix → O(V²)
• Using min-priority queue / min-heap → O((V + E) log V)

Space Complexity

• Storing distances, visited array, and graph representation
• Space Complexity = O(V + E)

Advantages

• Provides the shortest path from the source to all vertices.
• Greedy and efficient.
• Works well for both sparse and dense graphs.

Disadvantages

• Only applicable to graphs with non-negative edge weights.
• For graphs with negative weight edges, the Bellman-Ford algorithm should be used.

Conclusion

Dijkstra’s Algorithm is an efficient greedy algorithm for solving the single-source shortest path problem. It is widely used in applications such as network routing, GPS navigation, and various optimization problems.

Some More: 

• POP- Introduction to Programming Using ‘C’
• DS – Data structure Using C
• OOP – Object Oriented Programming 
• Java Programming
• DBMS – Database Management System
• RDBMS – Relational Database Management System
• https://defineinfoloop.blogspot.com/?m=1