What is Dijkstra's algorithm? A simple guide with a game

If you are asking what is Dijkstra's algorithm, the short answer is this: it is a method for finding the cheapest path from one starting point to every other point in a weighted graph. "Cheapest" can mean shortest distance, least time or lowest cost. You choose the meaning with the edge weights. This guide explains the idea, works a small example by hand, shows the code shape, and then looks at a real game that runs it every fraction of a second.

What is Dijkstra's algorithm?

A graph is a set of nodes joined by edges. In a weighted graph, each edge has a cost. A road map is the classic picture: towns are nodes, roads are edges, and the weight is the distance or the travel time.

Dijkstra's algorithm answers one question: starting from node S, what is the lowest total cost to reach every other node? It also lets you recover the route. It works because of one rule. Once it picks the unvisited node with the smallest known distance, that distance is final, as long as no edge has a negative weight.

That condition matters. Every edge cost must be zero or positive. If an edge can have a negative cost, the "final" claim breaks and you need a different algorithm.

How Dijkstra's algorithm works step by step

The method keeps a distance for every node. At the start the source is 0 and everything else is infinity, meaning "not reached yet." Then you repeat a small loop.

1. Pick the unvisited node with the smallest distance. Call it the current node.
2. Look at each neighbour of the current node and compute the current distance plus the edge cost.
3. If that total is lower than the neighbour's stored distance, replace the stored distance. This is called relaxing the edge.
4. Mark the current node as visited. Its distance will not change again.
5. Stop when every reachable node is visited, or when you reach the one target you care about.

To rebuild the actual path, also store a "came from" note whenever you relax an edge. At the end, follow those notes backwards from the target to the source.

A worked example on a small weighted graph

Take five nodes named A, B, C, D and E, with these edges: A to B costs 4, A to C costs 1, C to B costs 2, B to D costs 1, C to D costs 5, and D to E costs 3. Start at A, so A is 0 and the rest are infinity.

• Visit A (0). B becomes 4 and C becomes 1.
• Visit C (1), the smallest unvisited. Going to B through C costs 1 + 2 = 3, which beats 4, so B becomes 3. Going to D costs 1 + 5 = 6, so D becomes 6.
• Visit B (3). Going to D costs 3 + 1 = 4, which beats 6, so D becomes 4.
• Visit D (4). Going to E costs 4 + 3 = 7, so E becomes 7.
• Visit E (7). Nothing is left to improve.

The finished graph: the green edges are the cheapest route from A to E, with a total cost of 7.

The best route from A to E is A, C, B, D, E. The direct edge from A to B was not the cheapest way to reach B. The algorithm found that by trying the cheap node first and letting it improve its neighbours.

Dijkstra's algorithm in code with a priority queue

The expensive part of the loop is step 1, finding the smallest unvisited distance. Scanning every node each time works, but it is slow on large graphs. A priority queue fixes that. It is a structure that hands you the smallest item quickly.

1. Create a dist map with every node set to infinity, and set dist[source] = 0.
2. Create a priority queue and push the pair (0, source).
3. While the queue is not empty, pop the pair with the smallest distance.
4. If that distance is larger than dist[node], skip it. It is a stale entry from an earlier, worse path.
5. For each neighbour, compute dist[node] + cost. If it is smaller than dist[neighbour], update it, record the parent and push the new pair.

The stale entry check in step 4 is a common stumbling block. Most standard queues cannot lower the priority of an item already inside, so you push a fresh entry and ignore the old one when it pops out. A sorted set lets you remove the old entry and insert the new one instead, so no check is needed.

Once it runs, write a few unit tests. The five-node graph above is a good first one: assert that E has distance 7 and that the path is A, C, B, D, E. Add a test for an unreachable node and one for two routes with equal cost.

Time cost and why the priority queue matters

Let V be the number of nodes and E the number of edges. With the simple "scan for the smallest" approach, the work grows with V squared. With a binary heap as the priority queue, it grows with (V + E) times log V. On a sparse graph, where E is not much bigger than V, that is a large saving.

Dijkstra vs breadth-first search and A*

Breadth-first search finds the path with the fewest steps. It treats every edge as equal. If every edge in your graph costs 1, it gives the same answer as Dijkstra's algorithm and is simpler. Once edges differ in cost, the fewest steps is no longer the cheapest route, and you need Dijkstra.

A* is a close relative. It adds a guess, called a heuristic, of how far each node is from the target, and it explores the most promising nodes first. That makes it faster when you have one source and one target and a good guess. Dijkstra's algorithm has no guess. It explores outward evenly, which is what you want when you need the distance to many nodes at once.

Dijkstra's algorithm in a game: Tank City Zero Day

Map software uses this family of algorithms to find routes over road networks, and games use it to move enemies. Any time a character must walk around walls toward a goal, there is likely a distance map behind it.

Tank City Reboot has a clean example in its second game, Tank City Zero Day. The arena is a grid of 25 by 25 cells. A function called BuildFlow runs Dijkstra's algorithm over those cells with a sorted set as the queue, and its own code comment gives the costs: a step costs 1, and a step onto firewall costs 4, because the firewall has to be shot through first.

Look at what those weights do. An enemy will take a detour that adds fewer than three steps rather than cross a firewall cell, but it will go through the wall when the detour is longer. Cells holding silicon, coolant or the core cannot be stood on, so they are skipped. Steps run in eight directions, and a diagonal step is skipped when either of the two cells it cuts across is blocked, so a route never clips the corner of a blocked cell.

The search also runs in a useful direction. It starts at the goal and works outward, filling each cell with its distance to that goal. Every enemy then does something very cheap: it steps to the neighbouring cell with the lowest number. One search serves every enemy that shares a goal. If you have read about memoization, the idea is related: compute the answer once, then look it up.

Different enemies use different goals:

• Botnet drones walk the map whose goal is your tank. It is rebuilt about every 0.3 seconds, because you keep moving.
• Worms and ransomware walk the map whose goal is the cells around the core. It is rebuilt, about 0.2 seconds later, whenever the walls change.

The walkers add a few rules on top. A walker skips a neighbour that another enemy is already heading to, so they spread out. A walker blocked by firewall keeps shooting at it. A walker blocked by something else for about 1.4 seconds steps to a random neighbour to get unstuck. The cryptominer does not walk at all, and the zero-day boss drifts instead of following the map.

The result is something you can test by playing. Shoot out the firewall in a cell and the cost there falls from 4 to 1, the map is rebuilt, and the worms' routes change to use the gap.

Frequently asked questions

What is Dijkstra's algorithm used for?

It finds the lowest-cost path from one starting node to every other node in a graph with non-negative edge costs. Common uses are route finding, network routing and enemy movement in games.

Can Dijkstra's algorithm handle negative weights?

No. The proof that a visited node's distance is final depends on edge costs never being negative. For graphs with negative edges you need a different algorithm.

Is Dijkstra's algorithm the same as breadth-first search?

Only when every edge has the same cost. Breadth-first search counts steps, while Dijkstra's algorithm adds up weights, so it gives the right answer when edges differ in cost.

Why use a priority queue in Dijkstra's algorithm?

It gives you the unvisited node with the smallest distance without scanning every node. That brings the work down to about (V + E) times log V.

Get started

The best way to understand a distance map is to push on it. Open Tank City Zero Day, shoot a hole through a firewall wall, and watch which way the worms go. Then build your own version on a small grid: give plain cells a cost of 1 and a wall you can break a cost of 4, and write the priority queue loop from the steps above. Test it with the five-node example first.

Play Tank City Reboot: it is free, plays in your browser on a computer or a phone, and needs no account.