FREE E LEARNING PLATFORM
☰ HOMEEXCEPTIONSOOPSJVMINTRO
SYLLABUS TUTORIALS FORUM
 

Dijkstra's Algorithm



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 connected weighted graph. It always selects the vertex having the minimum tentative distance and updates the distances of its adjacent vertices until the shortest path to every vertex is determined.

The algorithm works only for graphs having non-negative edge weights. Due to its efficiency and simplicity, Dijkstra's Algorithm is widely used in computer networks, GPS navigation systems, transportation networks and routing protocols.

Why Do We Need Dijkstra's Algorithm?

Many real-life applications require finding the shortest or least expensive route between two locations. Dijkstra's Algorithm helps in selecting the minimum-cost path quickly and efficiently.

Application Purpose
GPS Navigation Finding the shortest route between two locations.
Computer Networks Routing packets through the shortest path.
Airline Route Planning Selecting minimum travel distance.
Transportation Systems Finding the shortest road network.
Robot Navigation Determining the optimal movement path.

Prerequisites

Concept Description
Graph A collection of vertices connected by weighted edges.
Weighted Graph Each edge has an associated cost or distance.
Greedy Method Selects the best available choice at every step.
Priority Queue Efficiently selects the minimum distance vertex.

Working Principle

Dijkstra's Algorithm starts from the source vertex and assigns a distance of 0 to it. All other vertices are assigned an infinite distance. At every iteration, the algorithm selects the unvisited vertex having the smallest distance and updates the distances of its neighbouring vertices whenever a shorter path is found.

The process continues until every vertex has been visited and the shortest distance from the source to every other vertex has been calculated.

Illustration


          A
       4 / \ 2
        /   \
       B-----C
       |     |
     5 |     |3
       |     |
       D-----E
          1

Source Vertex : A

Shortest Paths

A → C = 2

A → B = 4

A → E = 5

A → D = 6

Figure 1 : Shortest Paths using Dijkstra's Algorithm

Step-by-Step Example

Iteration Selected Vertex Distance from A
1 A 0
2 C 2
3 B 4
4 E 5
5 D 6

Dijkstra's Algorithm

Dijkstra(Graph, Source) Step 1 : Assign distance 0 to the source vertex. Step 2 : Assign infinite distance to all other vertices. Step 3 : Mark all vertices as unvisited. Step 4 : Select the unvisited vertex having the minimum distance. Step 5 : Update the distances of all adjacent vertices. Step 6 : Mark the selected vertex as visited. Step 7 : Repeat Steps 4 to 6 until all vertices are visited. Step 8 : Display the shortest distance from the source to every vertex.

Complexity Analysis

Implementation Time Complexity Remarks
Adjacency Matrix O(V²) Suitable for small and dense graphs.
Binary Heap + Adjacency List O((V + E) log V) Most commonly used implementation.
Fibonacci Heap O(E + V log V) Provides better theoretical performance.
Space Complexity O(V) Stores distance, parent and visited arrays.

Advantages of Dijkstra's Algorithm

  • Efficiently finds the shortest path from a single source.
  • Produces the optimal shortest path for graphs with non-negative edge weights.
  • Easy to understand and implement.
  • Suitable for large communication and transportation networks.
  • Widely used in routing and navigation systems.

Limitations of Dijkstra's Algorithm

  • Cannot handle negative edge weights.
  • Applicable only to weighted graphs.
  • Computational cost increases for extremely large graphs.
  • Bellman-Ford Algorithm is preferred when negative edge weights are present.

Applications of Dijkstra's Algorithm

Application Description
GPS Navigation Finding the shortest route between two locations.
Internet Routing Routing packets through the shortest available path.
Airline Networks Finding minimum travel distance.
Transportation Systems Optimizing road and railway routes.
Robot Navigation Determining the shortest movement path.

Dijkstra's Algorithm vs Bellman-Ford Algorithm

Dijkstra's Algorithm Bellman-Ford Algorithm
Uses Greedy Method. Uses Dynamic Relaxation.
Does not support negative edge weights. Supports negative edge weights.
Generally faster. Comparatively slower.
Cannot detect negative cycles. Can detect negative weight cycles.
Best for non-negative weighted graphs. Best for graphs containing negative weights.

Important Points

  • Dijkstra's Algorithm is a Greedy Algorithm.
  • It computes the shortest path from a single source vertex.
  • The algorithm always selects the unvisited vertex having the minimum distance.
  • It works only when all edge weights are non-negative.
  • Priority Queue improves the efficiency of the algorithm.
  • It is widely used in network routing and navigation systems.

Exam Tip

AKTU examinations frequently ask students to solve a weighted graph using Dijkstra's Algorithm and compare it with Bellman-Ford Algorithm. Remember that Dijkstra's Algorithm does not support negative edge weights, whereas Bellman-Ford Algorithm can handle them and can also detect negative weight cycles.

Summary

Dijkstra's Algorithm is one of the most widely used Greedy Algorithms for finding the shortest path from a single source vertex. It repeatedly selects the nearest unvisited vertex and updates the distances of adjacent vertices until the shortest paths to all vertices are obtained. The algorithm is efficient, easy to implement and extensively used in navigation systems, computer networks and transportation planning.







Copyright 2020 by Noidatut. All Rights Reserved.

Noidatut.com