Dijkstra’s Shortest Path Algorithm

In the previous lesson, we learned Huffman Coding and saw how greedy algorithms can optimize real-world systems like compression.

In this lesson, we move into one of the most important graph algorithms — Dijkstra’s Shortest Path Algorithm.

This algorithm helps us find the shortest path from a source node to all other nodes in a graph.

Why Shortest Path Problems Matter

Shortest path problems appear everywhere in real life.

For example:

• Google Maps finding the fastest route
• Network routing in the internet
• Logistics and delivery optimization
• Flight scheduling

Dijkstra’s Algorithm is the foundation behind many of these systems.

What Problem Does Dijkstra Solve?

Given a graph with non-negative edge weights, Dijkstra’s Algorithm computes the shortest distance from a starting node to every other node.

Important condition:

Dijkstra’s Algorithm does NOT work with negative edge weights.

Greedy Idea Behind the Algorithm

Dijkstra’s Algorithm follows a greedy strategy.

At each step, it selects the node with the smallest known distance from the source that has not yet been processed.

Once selected, this distance is considered final.

This greedy choice guarantees optimal results because all edge weights are non-negative.

Conceptual Working

Think of Dijkstra’s Algorithm as gradually expanding a safe zone around the source node.

Each step confirms the shortest distance to one new node.

The algorithm keeps improving distance estimates until no shorter paths are possible.

Algorithm Steps (High Level)

1. Initialize distances of all nodes to infinity.
2. Set the source node distance to zero.
3. Use a priority queue to pick the nearest unvisited node.
4. Relax edges of the selected node.
5. Repeat until all nodes are processed.

Pseudocode

initialize distance[source] = 0
initialize distance[others] = infinity
initialize priority queue pq

while pq is not empty:
    u = extract node with minimum distance
    for each neighbor v of u:
        if distance[u] + weight(u,v) < distance[v]:
            distance[v] = distance[u] + weight(u,v)
            update pq

The process of updating distances is called relaxation.

Real-World Example

Imagine a city with intersections as nodes and roads as edges.

Each road has a travel time.

Dijkstra’s Algorithm calculates the shortest travel time from your home to every other location in the city.

Once a route is finalized, it never needs to be reconsidered.

Why Negative Weights Break Dijkstra

Dijkstra assumes that once the shortest distance to a node is found, it will never change.

Negative weights violate this assumption by allowing paths to become shorter later.

For such cases, algorithms like Bellman–Ford are used instead.

Time Complexity

Using a priority queue:

O((V + E) log V)

Where:

V = number of vertices
E = number of edges

Mini Practice

Think about this carefully:

• Why is it safe to finalize a node’s distance?
• What would happen if a negative edge existed?

Exercises

Quick Quiz

Dijkstra’s Algorithm is a cornerstone of graph theory and real-world routing systems.

In the next lesson, we will extend this idea and learn about Dynamic Programming concepts starting with its introduction.