📘 Shortest Paths in Graphs: Dijkstra’s Algorithm

1️⃣ Introduction

Dijkstra’s Algorithm is a greedy algorithm used to find the shortest path from a single source vertex to all other vertices in a weighted graph.

🔹 Key Condition

✔ All edge weights must be non-negative

2️⃣ Problem Statement

Given:

A graph G(V, E)
A source vertex s
Edge weights w(u, v)

Objective:

Find the minimum distance from source s to all other vertices.

3️⃣ Key Idea of Dijkstra Algorithm

Maintain a set of visited vertices
Always pick the vertex with the minimum distance
Update distances of its neighbors

Greedy choice: select the closest unvisited vertex

4️⃣ Working Principle

🔹 Steps

Initialize distances:
- Source = 0
- Others = ∞
Mark all vertices as unvisited
Select vertex with minimum distance
Update distances of adjacent vertices
Mark vertex as visited
Repeat until all vertices are processed

5️⃣ Algorithm (Dijkstra)

🔹 Pseudocode

Dijkstra(G, s):
   for each vertex v:
       dist[v] = ∞
       visited[v] = false

   dist[s] = 0

   for i = 1 to V:
       u = vertex with minimum dist[u] not visited
       mark u as visited

       for each neighbor v of u:
           if not visited[v] and dist[u] + w(u,v) < dist[v]:
               dist[v] = dist[u] + w(u,v)

6️⃣ Example

🔹 Graph

      (A)
     /   \
   4/     \1
   /       \
 (B)---2---(C)
   \       /
    \5   3/
     \   /
      (D)

🔹 Source = A

🔹 Step-by-Step Distances

Vertex	Distance
A	0
B	4
C	1
D	4

✔ Shortest paths found

7️⃣ Time Complexity

🔹 Using Adjacency Matrix

[
O(V^2)
]

🔹 Using Min Heap (Priority Queue)

[
O((V + E) \log V)
]

✔ More efficient for large graphs

8️⃣ Space Complexity

Distance array → O(V)
Visited array → O(V)

9️⃣ Characteristics of Dijkstra Algorithm

✔ Greedy approach
✔ Works for weighted graphs
✔ Does not work for negative weights
✔ Finds shortest path from one source

🔟 Advantages

Efficient and widely used
Simple to implement
Works well for real-world problems

1️⃣1️⃣ Disadvantages

✖ Cannot handle negative edge weights
✖ Not suitable for all graph types
✖ Needs priority queue for efficiency

1️⃣2️⃣ Applications

GPS navigation systems
Network routing (Internet)
Shortest path in maps
Robotics and AI pathfinding
Telecommunications

1️⃣3️⃣ Comparison with Other Algorithms

Algorithm	Handles Negative Weights	Complexity
Dijkstra	✖ No	O(V²) / O(E log V)
Bellman-Ford	✔ Yes	O(VE)
Floyd-Warshall	✔ Yes	O(V³)

🔚 Conclusion

Dijkstra’s Algorithm is one of the most efficient methods for finding shortest paths in graphs with non-negative weights.

It uses a greedy approach to always expand the nearest vertex first.

📌 Exam Tip

👉 Always include:

Greedy nature
Non-negative condition
Algorithm steps
Example
Complexity

Shortest paths in graphs: Dijkstra algorithm