Dijkstra Algorithm Explained Simply: Shortest Path Made Easy

Introduction

Think about the last time you opened Google Maps and asked it for the fastest route. You typed in a destination, hit go, and within a second or two, you had turn-by-turn directions through a city with thousands of roads and intersections. What made that instant calculation possible is not magic. It is a fifty-year-old algorithm invented by a Dutch computer scientist named Edsger W. Dijkstra, during a twenty-minute coffee break in 1956.

If you have been trying to learn programming, crack a technical interview, or just understand how the internet actually routes your data from one server to another, this is one of the most important algorithms you will ever encounter. The problem is that most explanations online treat it like a math lecture, full of abstract notation that makes your eyes glaze over. This post does the opposite.

By the end of this guide, you will understand exactly how Dijkstra's algorithm works, why it works, where it is used in the real world, and how to think through it step by step without needing a computer science degree. Let's get into it.

What Problem Does It Actually Solve?

Before jumping into how the algorithm works, it helps to understand the specific problem it was designed to fix.

Imagine you are standing in a city with a paper map. You want to get from your hotel to a restaurant, and there are dozens of possible routes. Some routes are short but have a lot of traffic. Others are longer but fast. A few roads are one-way or under construction. How do you find the single fastest path from where you are to where you want to go?

This is called the Single Source Shortest Path problem. Given a starting point, you want to find the shortest (or cheapest, or fastest) path to every other point in a network. Dijkstra's algorithm solves this problem efficiently, and it does so on what computer scientists call a weighted graph.

What Is a Weighted Graph?

A graph in computer science is just a collection of nodes (also called vertices) and the connections between them (called edges). A weighted graph means each connection has a number attached to it, representing cost, distance, or time.

For example, think of five cities: A, B, C, D, and E. Roads connect them, and each road has a distance in kilometers. Your job is to find the shortest total distance from city A to city E. That is the classic setup for Dijkstra's algorithm.

The Core Idea Behind Dijkstra's Algorithm

Here is the key insight that makes the algorithm brilliant: it always processes the closest unvisited node first.

It works greedily. At every step, it picks whichever node it can reach with the minimum total cost so far. By doing this consistently, it builds up the shortest paths from the source node outward, like a wave expanding across the graph. By the time it finishes, every node has the shortest possible distance recorded.

The algorithm never wastes time reconsidering paths that have already been finalized. Once a node is marked as visited, its shortest distance is locked in forever. This is the property that makes it both efficient and correct.

Step-by-Step Walkthrough with a Real Example

Let us use a concrete example with six nodes labeled A through F. Imagine these as cities on a map, and the numbers on the roads are travel times in minutes.

The connections and their weights are:

•       A to B: 4 minutes

•       A to C: 2 minutes

•       B to D: 5 minutes

•       C to B: 1 minute

•       C to D: 8 minutes

•       D to E: 2 minutes

•       B to E: 6 minutes

We want to find the shortest path from A to E. Here is how Dijkstra's algorithm works through it.

Step 1 — Set Up Initial Distances

Start by assigning a distance of zero to the source node (A) and infinity to every other node. This represents the fact that we do not know how far anything is yet.

•       A = 0

•       B = infinity

•       C = infinity

•       D = infinity

•       E = infinity

Mark all nodes as unvisited.

Step 2 — Visit the Node with the Smallest Distance

The unvisited node with the smallest distance right now is A, with a distance of 0. We visit A and look at all its neighbors.

•       A connects to B with cost 4. Update B's distance to 0 + 4 = 4.

•       A connects to C with cost 2. Update C's distance to 0 + 2 = 2.

Mark A as visited. Current distances: A=0, B=4, C=2, D=infinity, E=infinity.

Step 3 — Move to the Next Closest Node

The unvisited node with the smallest distance is now C with a distance of 2. Visit C and check its neighbors.

•       C connects to B with cost 1. Total = 2 + 1 = 3. Since 3 is less than B's current distance of 4, update B to 3.

•       C connects to D with cost 8. Total = 2 + 8 = 10. Update D to 10.

Mark C as visited. Current distances: A=0, B=3, C=2, D=10, E=infinity.

Step 4 — Continue the Process

Next smallest unvisited is B with distance 3. Visit B and check its neighbors.

•       B connects to D with cost 5. Total = 3 + 5 = 8. Since 8 is less than D's current distance of 10, update D to 8.

•       B connects to E with cost 6. Total = 3 + 6 = 9. Update E to 9.

Mark B as visited. Current distances: A=0, B=3, C=2, D=8, E=9.

Step 5 — Visit D

Next smallest unvisited is D with distance 8. Visit D.

•       D connects to E with cost 2. Total = 8 + 2 = 10. Since 10 is greater than E's current distance of 9, we do not update E.

Mark D as visited. Current distances: A=0, B=3, C=2, D=8, E=9.

Step 6 — Visit E

Visit E with distance 9. E has no outgoing connections in our example. Mark as visited. Algorithm complete.

Final Answer

Shortest Path Result:

The shortest path from A to E is 9 minutes. The route is A -> C -> B -> E, with distances 0 + 2 + 1 + 6 = 9.

Where Is This Algorithm Used in Real Life?

Dijkstra's algorithm is not just a classroom exercise. It powers real systems used by billions of people every day.

Navigation and Mapping

Google Maps, Apple Maps, and Waze all use variations of Dijkstra's algorithm under the hood. When you ask for the fastest route, the map treats every intersection as a node and every road segment as a weighted edge. The algorithm finds the path with the lowest total travel time, accounting for distance, speed limits, and live traffic.

Internet Routing

When you send a message or load a webpage, your data travels through dozens of routers across the internet. The OSPF protocol (Open Shortest Path First), which many internet routers use, is directly based on Dijkstra's algorithm. It ensures your data takes the shortest path through the network.

Game Development

In video games, characters need to find their way around obstacles and terrain. AI-controlled enemies and NPCs use pathfinding algorithms, often based on Dijkstra's or its close cousin A-star, to navigate efficiently through a game world.

Flight Booking Systems

Airlines and booking platforms model their route networks as graphs, with ticket prices or layover times as edge weights. Finding the cheapest flight with connections is a shortest path problem, and Dijkstra's algorithm is often part of the solution.

Social Networks

Platforms like LinkedIn measure connection degrees (first, second, third connections) using graph traversal algorithms. Finding the shortest connection path between you and a potential contact involves the same logic.

Implementing Dijkstra in Python: Code Walkthrough

Ready to code? Here's simple Python using a priority queue (heapq). No libraries needed beyond basics.

python
import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]  # (distance, node)
    prev = {node: None for node in graph}
    
    while pq:
        current_dist, u = heapq.heappop(pq)
        if current_dist > distances[u]:
            continue
        
        for v, weight in graph[u].items():
            alt = current_dist + weight
            if alt < distances[v]:
                distances[v] = alt
                prev[v] = u
                heapq.heappush(pq, (alt, v))
    
    return distances, prev

# Example graph: dict of dicts
graph = {
    'A': {'B': 4, 'C': 2},
    'B': {'D': 3, 'E': 5},
    'C': {'D': 1, 'E': 5},
    'D': {},
    'E': {}
}

distances, prev = dijkstra(graph, 'A')
print(distances)  # {'A': 0, 'B': 4, 'C': 2, 'D': 3, 'E': 7}

This runs in O((V+E) log V)—efficient for most cases. Trace paths backward via prev.

Test it: Add nodes, tweak weights. Beginners: Copy-paste into Jupyter.

Time and Space Complexity

Understanding how efficient Dijkstra's algorithm is matters a lot in real-world applications.

•       With a basic implementation using an array: O(V squared) time, where V is the number of vertices.

•       With a priority queue (min-heap): O((V + E) log V), where E is the number of edges. This is far more efficient for large, sparse graphs.

•       Space complexity: O(V) to store distances and the visited set.

For most practical use cases like maps and routers with millions of nodes, the priority queue version is what gets used.

Important Limitation — No Negative Weights

There is one critical limitation you must know: Dijkstra's algorithm does not work correctly if any edge in the graph has a negative weight.

The reason is that the algorithm's core assumption is that once a node is visited, its shortest path is finalized. Negative edges can create shortcuts that appear after a node has already been visited, breaking this guarantee.

If your graph has negative weights, you need to use the Bellman-Ford algorithm instead. It is slower but handles negative weights correctly.

Common Mistakes Beginners Make

After helping dozens of people understand this algorithm, here are the mistakes that come up most often.

Forgetting to Initialize Distances to Infinity

If you initialize all distances to zero instead of infinity, the algorithm has no way to distinguish between the source node and unvisited nodes. Every comparison breaks down. Always start with infinity for every node except the source.

Not Using a Priority Queue

A naive implementation loops through all nodes to find the smallest distance each time. This works but is extremely slow. Using a min-heap (priority queue) is what makes the algorithm practical for real-world graphs.

Revisiting Already Processed Nodes

Once a node has been visited and its shortest distance finalized, do not process it again. A common bug is failing to skip nodes that are already processed when they are popped from the priority queue multiple times with outdated distances.

Applying It to Graphs with Negative Weights

As mentioned above, Dijkstra's algorithm gives incorrect results on graphs with negative edges. This is a logic error, not a code error, and it is easy to overlook when building something like a financial cost model.

Confusing It with BFS

Breadth-first search finds the shortest path by number of hops (edges), not by total weight. Dijkstra finds the shortest path by total edge weight. They are similar in structure but solve different problems. Do not use BFS on weighted graphs and expect it to work correctly.

Dijkstra vs. A-Star — When to Use Which

Once you understand Dijkstra, the natural next question is about A-star (A*), which is a popular extension.

•       Dijkstra explores in all directions equally, finding the absolute shortest path from the source to all nodes.

•       A-star uses a heuristic (like straight-line distance) to guide the search toward the destination more directly, making it faster when you only need one specific destination.

•       Dijkstra is better when you need shortest paths to all nodes from a single source.

•       A-star is better for point-to-point navigation where speed matters and a good heuristic exists.

In practice, Google Maps and similar systems use more advanced variations of both depending on the specific optimization needed.

Pro Tips for Interviews and Real Projects

If you are preparing for a technical interview or building something that uses graph traversal, here are strategies that will actually help.

1.    Always draw the graph first. Before writing any code, sketch the nodes and edges on paper. Visualization makes the logic much clearer and helps catch errors early.

2.    Practice with adjacency lists, not just matrices. Most interview problems and real codebases use adjacency lists for sparse graphs. Get comfortable with dictionary-of-dictionaries representations.

3.    Know when to stop early. If you only need the shortest path to one specific node, you can stop the algorithm as soon as that node is visited. This optimization is worth mentioning in interviews.

4.    Trace through examples by hand. Do not just run the code and trust it. Trace through the steps manually with a small example first. It builds intuition and catches off-by-one errors.

5.    Understand the variants. Be ready to discuss Bellman-Ford for negative weights, A-star for heuristic search, and Floyd-Warshall for all-pairs shortest paths. Knowing the landscape shows depth.

Conclusion

Dijkstra's algorithm is one of those rare ideas that is both elegant and massively practical. It was conceived in under half an hour and is now embedded in systems that billions of people interact with every single day. Understanding it is not just about passing an exam or an interview. It genuinely changes how you think about problems involving networks, optimization, and graphs.

The core idea is simple: always go to the closest unvisited place first, update your distance estimates as you go, and never look back once a node is finalized. That's it. Everything else is implementation detail.

Start with the example in this post. Then code it from scratch in Python. Then try modifying it for a custom graph of your own. By the time you've done those three things, this algorithm will feel like second nature.

FAQ

Q1: What is Dijkstra's algorithm in simple terms?

Dijkstra's algorithm finds the shortest path between two points in a network. It works by starting at your source node, then always moving to the closest unvisited node, updating distance estimates along the way. Think of it as a very smart GPS that evaluates every possible route and keeps choosing the cheapest next step.

Q2: What is Dijkstra's algorithm used for in the real world?

It is used in GPS navigation (Google Maps, Waze), internet routing protocols (OSPF), airline booking systems, video game AI pathfinding, and social network analysis. Any time a system needs to find the shortest or cheapest path through a network, Dijkstra's algorithm or one of its variants is usually involved.

Q3: Does Dijkstra's algorithm work with negative weights?

No. Dijkstra's algorithm assumes all edge weights are non-negative. If any edge has a negative weight, the algorithm can produce incorrect results. For graphs with negative weights, use the Bellman-Ford algorithm instead, which handles this case correctly though it is slower.

Q4: What is the time complexity of Dijkstra's algorithm?

With a basic array implementation, it runs in O(V squared) time. With a min-heap (priority queue), it runs in O((V + E) log V) time, where V is the number of vertices and E is the number of edges. The priority queue version is what is used in production systems.

Q5: What is the difference between Dijkstra and BFS?

Breadth-first search (BFS) finds the shortest path measured by number of edges, treating all edges equally. Dijkstra's algorithm finds the shortest path measured by total edge weight, making it suitable for weighted graphs. If all edges have equal weight, Dijkstra and BFS give the same result, but BFS is simpler to implement for that case.