Dijkstra's Algorithm

Grokking Graph Algorithms for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Dijkstra's Algorithm

Table of Contents

Contents are not accessible

Dijkstra’s Algorithm is a famous algorithm used to find the shortest path from a source node to all other nodes in a graph. It was created by Edsger W. Dijkstra in 1956. This algorithm is commonly used in network routing protocols and geographic information systems (GIS).

Key Points

It finds the shortest path from a single source node to all other nodes.
It works on graphs with non-negative weights.
It uses a priority queue to explore the next most promising node.
It ensures that once a node's shortest path is found, it is not updated again.

Can Dijkstra’s Algorithm Work on Both Directed and Undirected Graphs?

Yes, Dijkstra’s Algorithm can work on both directed and undirected graphs.

1. Directed Graphs:

In a directed graph, edges have a direction, meaning the path from node A to node B is not the same as the path from node B to node A.
Dijkstra's Algorithm can handle this by considering the direction of each edge during its calculations.

Example:

A --> B (weight 3)
A --> C (weight 1)
C --> B (weight 1)

In this example, the shortest path from A to B goes through C (A -> C -> B) with a total weight of 2.

2. Undirected Graphs:

In an undirected graph, edges do not have a direction, meaning the path from node A to node B is the same as the path from node B to node A.
Dijkstra's Algorithm treats these edges as bidirectional paths during its calculations.

Example:

A -- B (weight 3)
A -- C (weight 1)
C -- B (weight 1)

In this example, the shortest path from A to B can go either directly (A -> B) with a weight of 3, or through C (A -> C -> B) with a total weight of 2. Here, you can also go from A -> B and B -> C.

How Does Dijkstra's Algorithm Works?

Dijkstra's Algorithm particularly useful for graphs with non-negative edge weights and is commonly employed in various applications such as network routing, geographic information systems, and more.

The core idea of Dijkstra's Algorithm is to iteratively select the node with the smallest known distance from the source, explore its neighbors, and update their distances if a shorter path is found. This process continues until all nodes have been processed or the shortest path to the desired node has been found.

The algorithm uses a priority queue (often implemented as a min-heap) to efficiently fetch the next node with the smallest known distance. The distance to each node is updated if a shorter path is discovered through the current node. Once a node's shortest path is determined, it is marked as "visited," and its distance is not updated again.

Step-by-Step Algorithm

Initialize:
- Create a distance array dist[] and initialize all distances to infinity, except for the source node which is set to 0.
- Create a priority queue (min-heap) and insert the source node with a distance of 0.
Process Nodes:
- While the priority queue is not empty:
  - Extract the node u with the minimum distance from the priority queue.
  - For each neighbor v of node u, with edge weight weight:
    - If the distance to v through u is less than the known distance to v, update the distance to v.
    - Insert or update the neighbor v in the priority queue with the new distance.
Completion:
- Repeat the process until all nodes have been processed or the priority queue is empty.
- The distance array dist[] now contains the shortest distances from the source node to all other nodes.

Algorithm Walkthrough

Let's walk through Dijkstra's Algorithm using the same example as in the code:

Consider the following graph represented as an adjacency list:

0: [(1, 1), (2, 4)]
1: [(2, 2), (3, 6)]
2: [(3, 3)]
3: [(4, 1)]
4: [(5, 2)]
5: []

Initialization:
- Source node: 0
- Distance array: dist[] = [0, ∞, ∞, ∞, ∞, ∞]
- Priority queue: [(0, 0)] (vertex 0 with distance 0)
Iteration 1:
- Extract 0 with distance 0.
- Neighbors of 0: 1 (1), 2 (4).
- Update distances: dist[] = [0, 1, 4, ∞, ∞, ∞]
- Update priority queue: [(1, 1), (2, 4)]
Iteration 2:
- Extract 1 with distance 1.
- Neighbors of 1: 2 (2), 3 (6).
- Update distances: dist[] = [0, 1, 3, 7, ∞, ∞]
- Update priority queue: [(2, 3), (2, 4), (3, 7)] (notice 2 is inserted again with a shorter distance)
Iteration 3:
- Extract 2 with distance 3.
- Neighbors of 2: 3 (3).
- Update distances: dist[] = [0, 1, 3, 6, ∞, ∞]
- Update priority queue: [(2, 4), (3, 6), (3, 7)]
Iteration 4:
- Extract 2 with distance 4.
- Neighbors of 2 are already processed with a shorter distance.
- No updates needed.
- Update priority queue: [(3, 6), (3, 7)]
Iteration 5:
- Extract 3 with distance 6.
- Neighbors of 3: 4 (1).
- Update distances: dist[] = [0, 1, 3, 6, 7, ∞]
- Update priority queue: [(3, 7), (4, 7)]
Iteration 6:
- Extract 3 with distance 7.
- Neighbors of 3 are already processed with a shorter distance.
- No updates needed.
- Update priority queue: [(4, 7)]
Iteration 7:
- Extract 4 with distance 7.
- Neighbors of 4: 5 (2).
- Update distances: dist[] = [0, 1, 3, 6, 7, 9]
- Update priority queue: [(5, 9)]
Iteration 8:
- Extract 5 with distance 9.
- Neighbors of 5 are already processed.
- No updates needed.
- Priority queue is now empty.
Completion:
- The priority queue is empty, and the algorithm terminates.
- The final shortest distances from source node 0 are: [0, 1, 3, 6, 7, 9].

Code

Python3

. . . .

Complexity Analysis

Time Complexity

Each vertex is inserted and extracted from the priority queue at most once, resulting in $O(V \log V)$ operations.
Each edge is processed once, resulting in $O(E \log V)$ operations.
Using a priority queue (min-heap), the algorithm runs in $O((V + E) \log V)$ where (V) is the number of vertices and (E) is the number of edges.

Space Complexity

The distance array and the priority queue each use $O(V)$ space.

Why Dijkstra’s Algorithm Fails for Graphs with Negative Edges?

Dijkstra’s Algorithm is designed to find the shortest path in a graph with non-negative edge weights. However, when the graph contains negative edge weights, the algorithm can fail to produce correct results. This failure is primarily due to the way the algorithm prioritizes and updates distances. Here's an in-depth explanation along with an illustrative graph.

The Problem with Negative Edges

Dijkstra's Algorithm assumes that once a node's shortest path is determined, it will not change. This assumption holds true only for graphs with non-negative edge weights. When negative edge weights are present, a shorter path may be found after a node has already been processed, leading to incorrect results.

Illustration with an Example Graph

Consider the following graph:

      4         2
A -------> B -------> C
|          |         |
|          |         |
|5         |-3       |
|          |         |
v          v     -3  v
D <------- E <-------
    -2

In this graph:

Vertex A is connected to B with a weight of 4.
Vertex B is connected to C with a weight of 2.
Vertex B is connected to E with a weight of -3.
Vertex C is connected to E with a weight of -3.
Vertex E is connected to D with a weight of -2.
Vertex A is connected to D with a weight of 5.

Step-by-Step Walkthrough with Dijkstra's Algorithm

Let's use Dijkstra's Algorithm starting from vertex A to find the shortest path to all other vertices.

Initialization:
- Source node: A
- Distance array: dist[] = [0, ∞, ∞, ∞, ∞]
- Priority queue: [(A, 0)]
Iteration 1:
- Extract A with distance 0.
- Neighbors of A: B (4), D (5).
- Update distances: dist[] = [0, 4, ∞, 5, ∞]
- Update priority queue: [(B, 4), (D, 5)]
Iteration 2:
- Extract B with distance 4.
- Neighbors of B: C (2), E (-3).
- Update distances: dist[] = [0, 4, 6, 5, 1] (E is updated incorrectly)
- Update priority queue: [(D, 5), (C, 6), (E, 1)]
Iteration 3:
- Extract E with distance 1.
- Neighbors of E: D (-2).
- Update distances: dist[] = [0, 4, 6, -1, 1]
- Update priority queue: [(D, -1), (C, 6)]
Iteration 4:
- Extract D with distance -1.
- D has no neighbors.
- No updates needed.
Iteration 5:
- Extract C with distance 6.
- Neighbors of C: E (-3).
- Update distances: No shorter paths found.
- Priority queue is now empty.

Explanation of the Failure

Here, the shortest path from A to D is negative, which shouldn't be. This incorrect processing occurs because Dijkstra's Algorithm does not handle the relaxation process correctly in the presence of negative weights. It relies on the assumption that once a node is processed, its shortest path is finalized, which is not true for graphs with negative edges.

Real-time Applications of Dijkstra’s Algorithm

Dijkstra's Algorithm is widely used in various real-world applications due to its efficiency in finding the shortest paths in graphs with non-negative edge weights. Here are some key applications:

GPS Navigation Systems:
- Finds the shortest path between locations.
- Optimizes route planning for quickest travel time.
Network Routing Protocols:
- Used in OSPF (Open Shortest Path First) for data packet routing.
- Ensures efficient use of network resources and reduces delays.
Geographic Information Systems (GIS):
- Determines shortest paths in spatial databases.
- Aids in urban planning, disaster management, and transportation logistics.
Airline Flight Scheduling:
- Schedules flights efficiently between airports.
- Minimizes costs and optimizes travel times considering constraints.
Emergency Response Systems:
- Calculates quickest routes for emergency vehicles.
- Improves response times during emergencies.
Logistics and Supply Chain Management:
- Optimizes delivery routes for transportation companies.
- Reduces delivery times and transportation costs.
Public Transportation Systems:
- Plans optimal routes for buses and trains.
- Enhances scheduling efficiency and reduces travel times for commuters.
Telecommunications Networks:
- Manages data flow in telecommunications networks.
- Ensures optimal use of bandwidth and reduces latency.

Now, let's start solving problems related to Dijkstra’s Algorithm

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible