# Dijkstra's Shortest Path Algorithm by [ kirupa](//www.kirupa.com/me/index.htm)   |   filed under [Data Structures and Algorithms](https://www.kirupa.com/data_structures_algorithms/index.htm) If you have ever used a maps app to figure out the best route somewhere, you have already bumped into the kind of problem Dijkstra's shortest path algorithm is really good at solving. Given a starting point and a destination, we don't just want ***a*** path. We want the ***cheapest*** path. In the following sections, we'll learn how Dijkstra's algorithm works, why our earlier graph traversal approaches like BFS and DFS aren't enough by themselves, and how to implement everything in JavaScript using a weighted graph. Onwards! ## Meet Weighted Graphs Earlier, when we looked at [graphs](https://www.kirupa.com/data_structures_algorithms/graphs.htm) and then explored them using [DFS and BFS](https://www.kirupa.com/data_structures_algorithms/dfs_bfs.htm), the only thing we really cared about was whether a node was connected to another node. For shortest-path problems, we need one more detail attached to each edge. We need a **weight**. A weight is just a number that represents how expensive it is to travel along a particular edge. Depending on what our graph is modeling, that weight can mean distance, time, cost, traffic, danger, latency, or some other thing we want to minimize. Here is the weighted graph we are going to use for our walkthrough: ![​](https://www.kirupa.com/data_structures_algorithms/images/djikstra_example_200.png?q=1) In text form, with each node followed by its neighbors and the cost of reaching them in parentheses, the same graph looks as follows: ``` A: B(4), C(2) B: A(4), D(5) C: A(2), D(8), E(10) D: B(5), C(8), E(2), F(9) E: C(10), D(2), F(3) F: D(9), E(3) ``` If we describe the same graph in a less dramatic and more paperwork-friendly way, the edges look like this: | **Edge** | | **Weight** | | A - B | | 4 | | A - C | | 2 | | B - D | | 5 | | C - D | | 8 | | C - E | | 10 | | D - E | | 2 | | D - F | | 9 | | E - F | | 3 | Our goal is to get from node **A** to node **F** while spending the smallest total cost possible. One quick note about these pictures before we go on. Seeing the whole graph at once is a luxury reserved for us, the readers. The algorithm we are about to meet never gets this bird's-eye view. It discovers the graph one node at a time, and that detail shapes everything about how it works. We will keep coming back to this. ## Why BFS Isn't Enough BFS is amazing when every edge is effectively worth the same amount. It explores outward level by level, which means it will find the path with the fewest edges. That is perfect for unweighted graphs. Our current graph is not unweighted. Every edge has its own cost, and that changes everything. For example, a BFS-style mindset would be very happy with the path **A - C - E - F** because it uses only three edges. The total cost of that path is: ```javascript 2 + 10 + 3 = 15 ``` There is another route, **A - B - D - E - F**, that uses four edges instead of three. That sounds worse if we only care about hop count. The total cost here is: ```javascript 4 + 5 + 2 + 3 = 14 ``` Even though the second route uses more edges, it is actually cheaper overall. This is the exact sort of problem Dijkstra's algorithm is built for. It doesn't care about the fewest hops. It cares about the smallest total weight. ## How Dijkstra's Algorithm Thinks The core idea is pleasantly straightforward. Starting from our source node, we keep track of the best known cost to reach every other node. This is where that earlier note about the bird's-eye view matters. At any moment, the algorithm knows exactly three things: the node it is currently standing on, the edges leading out of that node, and the nodes it has taken so far. That's it. Everything else in the graph might as well be fog. The full map exists only on our side of the page. At the beginning, we only know two things for certain: - The distance from our start node to itself is **0** - The distance from our start node to every other node is **Infinity**, because we haven't discovered anything useful yet From there, Dijkstra's algorithm keeps repeating the following steps: - Pick the unvisited node with the smallest known distance - Look at each of its neighbors - See if going through the current node gives us a cheaper route to that neighbor - If it does, update that neighbor's distance and remember how we got there This update step has a fancy name: **relaxation**. It just means we found a better deal and replaced the more expensive route. One detail makes this all work: all edge weights must be **non-negative**. No weird negative shortcuts allowed. We'll revisit that restriction later. Before we turn the algorithm loose, take one more look at our graph. If you had to bet on the cheapest route from A to F right now, which one would you pick? Lock in your guess. We are about to find out whether it survives. ## It's Example Time Let's walk through our graph from earlier and find the cheapest path from **A** to **F**. ### Our Starting State We begin at node A. Its distance is **0**. Every other node gets **Infinity** because we have not found a route to them yet. | **Node** | | **Best Known Distance from A** | | **Previous Node** | | A | | 0 | | - | | B | | Infinity | | - | | C | | Infinity | | - | | D | | Infinity | | - | | E | | Infinity | | - | | F | | Infinity | | - | Now we explore A's neighbors. Standing at A, the only things the algorithm can see are the two edges leading out: one to B and one to C: ![​](https://www.kirupa.com/data_structures_algorithms/images/dijkstra_ex1_200.png) Even though we can see D, E, and F sitting right there in our diagram, the algorithm has no idea they exist yet: - A to B costs 4, so B becomes 4 - A to C costs 2, so C becomes 2 | **Node** | | **Best Known Distance from A** | | **Previous Node** | | A | | 0 | | - | | B | | 4 | | A | | C | | 2 | | A | | D | | Infinity | | - | | E | | Infinity | | - | | F | | Infinity | | - | The smallest unvisited node is now **C** with a cost of **2**. That is where we go next. ### Exploring C From C, we can reach D and E: ![​](https://www.kirupa.com/data_structures_algorithms/images/dijsktra_ex2_200.png) Take a moment to appreciate what just happened: two brand new nodes popped into view. A moment ago, the algorithm didn't know D and E existed. Now they are on the radar, each with a first cost estimate: - Going from A to C to D costs **2 + 8 = 10**, so D becomes 10 - Going from A to C to E costs **2 + 10 = 12**, so E becomes 12 | **Node** | | **Best Known Distance from A** | | **Previous Node** | | A | | 0 | | - | | B | | 4 | | A | | C | | 2 | | A | | D | | 10 | | C | | E | | 12 | | C | | F | | Infinity | | - | Our current cheapest unvisited node is now **B** with a cost of **4**. ### Exploring B From B, we can reach D with a cost of 5: ![​](https://www.kirupa.com/data_structures_algorithms/images/dijkstra_ex3_200.png) We already know one route to D, and it costs 10. Let's see if B gives us something better: ```javascript cost to reach B + edge from B to D 4 + 5 = 9 ``` That is cheaper than 10, so we update D. This is our first big Dijkstra moment. We found a better route to a node we had already seen before. And notice how little information that took. No peeking at the full map, no clever foresight. The algorithm stood at B, looked at a single edge, and compared two numbers in its notes. That tiny local comparison is the entire engine of this algorithm. | **Node** | | **Best Known Distance from A** | | **Previous Node** | | A | | 0 | | - | | B | | 4 | | A | | C | | 2 | | A | | D | | 9 | | B | | E | | 12 | | C | | F | | Infinity | | - | The smallest unvisited node is now **D** with a cost of **9**. ### Exploring D D gives us two interesting neighbors: ![​](https://www.kirupa.com/data_structures_algorithms/images/dijsktra_ex4_200.png) The distance to go here now is: - Going from A to B to D to E costs **9 + 2 = 11** - Going from A to B to D to F costs **9 + 9 = 18** E used to cost 12, so we improve it to 11. F used to be Infinity, so 18 is its first real value. | **Node** | | **Best Known Distance from A** | | **Previous Node** | | A | | 0 | | - | | B | | 4 | | A | | C | | 2 | | A | | D | | 9 | | B | | E | | 11 | | D | | F | | 18 | | D | The next smallest unvisited node is **E** with a cost of **11**. ### Exploring E From E, we can reach F for a cost of 3. Let's see if this beats the current 18: ![​](https://www.kirupa.com/data_structures_algorithms/images/djikstra_example_200.png?q=1) ```javascript cost to reach E + edge from E to F 11 + 3 = 14 ``` It absolutely does, so F gets updated from 18 to 14. | **Node** | | **Best Known Distance from A** | | **Previous Node** | | A | | 0 | | - | | B | | 4 | | A | | C | | 2 | | A | | D | | 9 | | B | | E | | 11 | | D | | F | | 14 | | E | At this point, F is the smallest unvisited node. Once we select it, we are done. Our cheapest route from A to F has a total cost of **14**. ### Reconstructing the Path The distance table tells us the total cost, but the **previous node** values tell us the route. Starting at F and walking backward: - F came from E - E came from D - D came from B - B came from A If we reverse that order, our final path (with the edge costs along the way) is: ```javascript A --4--> B --5--> D --2--> E --3--> F ``` Add those numbers up, and we get the same **14** from our distance table. Neat, right? ## The High-Level Algorithm We just spent a lot of time walking through the mechanics. If we compress everything we did into a simpler checklist, Dijkstra's algorithm looks like this: - Set the starting node's distance to 0 and every other node's distance to Infinity - Mark every node as unvisited - Pick the unvisited node with the smallest known distance - For each neighbor, calculate the cost of reaching it through the current node - If that cost is lower than the neighbor's current distance, update the distance and previous node - Mark the current node as visited - Repeat until there are no useful unvisited nodes left or we reach our destination That is the whole song and dance. ## A JavaScript Implementation Let's turn all of this into code. To keep things beginner-friendly, we are going to use a simple weighted graph implementation where each node stores an array of neighboring nodes and their corresponding weights. One implementation detail to keep an eye on is how we choose the next node to process. The most optimized versions of Dijkstra's algorithm use a [heap / priority queue](https://www.kirupa.com/data_structures_algorithms/heap.htm). We are not doing that right away. We will start with a more readable approach that scans all unvisited nodes to find the one with the smallest distance, and then upgrade to the heap-based version once the core logic feels comfortable. ```javascript class WeightedGraph { constructor() { this.nodes = new Map(); } addNode(node) { if (!this.nodes.has(node)) { this.nodes.set(node, []); } } addEdge(node1, node2, weight) { if (weight The heart of the algorithm lives inside the `dijkstra` method. The pieces worth remembering are: `distances` stores the best known cost to each node `previous` stores how we got to each node using our best route so far `visited` makes sure we don't keep reprocessing nodes we have already locked in ### Using the Code The following example recreates the graph from our walkthrough and finds the shortest path between A and F: ```javascript const graph = new WeightedGraph(); graph.addNode("A"); graph.addNode("B"); graph.addNode("C"); graph.addNode("D"); graph.addNode("E"); graph.addNode("F"); graph.addEdge("A", "B", 4); graph.addEdge("A", "C", 2); graph.addEdge("B", "D", 5); graph.addEdge("C", "D", 8); graph.addEdge("C", "E", 10); graph.addEdge("D", "E", 2); graph.addEdge("D", "F", 9); graph.addEdge("E", "F", 3); const result = graph.dijkstra("A", "F"); console.log(result.distance); // 14 console.log(result.path); // ["A", "B", "D", "E", "F"] ``` When you run this code, the output should look comfortingly familiar. The total cost is 14, and the path matches the one we manually discovered in the earlier walkthrough. ### Implementation Detail Our implementation is intentionally a little less fancy than what you might use in production. The reason is simple: it is easier to read. The `getClosestUnvisitedNode` method scans all nodes every time we need to find the next cheapest candidate. That repeated scanning is not the fastest thing in the universe, but it makes the algorithm much easier to understand. Once the idea clicks, the next upgrade is to replace that scan with a priority queue backed by a heap. That upgrade is exactly where we are headed next. ## Upgrading to a Priority Queue The slow part of our implementation is `getClosestUnvisitedNode`. Every single time we need the next cheapest node, we walk through every node we know about. It works, but it is the algorithmic equivalent of re-reading your entire to-do list from the top each time you finish a task. What we want instead is a to-do list that keeps itself sorted, where the cheapest item is always sitting right on top. That is exactly what a heap-backed priority queue gives us, and we already built most of it in the [Heap data structure](https://www.kirupa.com/data_structures_algorithms/heap.htm) article. The `Heap` class we created there needs only two small tweaks for Dijkstra duty: That heap was a **max**-heap, where the largest value bubbles to the top. Here we want the opposite, so every comparison flips and `extractMax` becomes `extractMin` That heap stored plain numbers. Here each entry is a `{ node, distance }` pair, so our comparisons look at the `distance` property With those changes applied, our min-heap looks like this: ```javascript class MinHeap { constructor() { // The heap is stored as an array this.heap = []; } // Add a new { node, distance } entry to the heap insert(value) { this.heap.push(value); this.#bubbleUp(this.heap.length - 1); } // Remove the entry with the smallest distance extractMin() { if (this.heap.length === 0) { return null; } if (this.heap.length === 1) { return this.heap.pop(); } const min = this.heap[0]; this.heap[0] = this.heap.pop(); this.#bubbleDown(0); return min; } #bubbleUp(index) { if (index === 0) { return; } const parentIndex = Math.floor((index - 1) / 2); if (this.heap[index].distance If you compare this side by side with the original `Heap` class, you'll see the bones are identical. The bubbling logic, the array representation, the parent and child index math, all of it carries over unchanged. Next, we give our `WeightedGraph` class a heap-powered version of the algorithm: ```javascript dijkstraWithHeap(startNode, endNode) { const distances = new Map(); const previous = new Map(); const visited = new Set(); const queue = new MinHeap(); for (const node of this.nodes.keys()) { distances.set(node, Infinity); previous.set(node, null); } distances.set(startNode, 0); queue.insert({ node: startNode, distance: 0 }); while (!queue.isEmpty()) { const currentNode = queue.extractMin().node; // A node can land in the queue more than once, so // skip any entry for a node we have already locked in if (visited.has(currentNode)) { continue; } if (currentNode === endNode) { break; } visited.add(currentNode); for (const neighbor of this.getNeighbors(currentNode)) { if (visited.has(neighbor.node)) { continue; } const newDistance = distances.get(currentNode) + neighbor.weight; if (newDistance The overall shape is the same as before. The one wrinkle worth calling out is that early `visited` check. When we find a cheaper route to a node, we don't reach into the heap and fix its old entry. We just toss in a new, cheaper entry and move on. That means stale duplicates can pile up in the queue, and when one of them eventually surfaces, we recognize it as old news and skip it. This trick goes by the name **lazy deletion**, which is also how I deal with most of my email. Calling `dijkstraWithHeap("A", "F")` on our example graph returns the exact same answer as before: a distance of **14** along the path **A, B, D, E, F**. Same result, much less busywork on large graphs. ## Performance Details There is one more thing before we wrap up, and that has to do with performance. ### The Version We Wrote **Runtime Complexity:** Finding the next cheapest unvisited node requires scanning all nodes, and we may do that many times. The overall time complexity for this version is typically described as O(|N|2 + |E|). **Memory Complexity:** We store our graph plus the `distances`, `previous`, and `visited` collections. That gives us a space complexity of **O(|N| + |E|)**. ### The Faster Version When we replace the repeated full scan with a min-priority queue, which is exactly what our `dijkstraWithHeap` version does, the runtime improves nicely. The common performance you will see for that version is: - **Runtime Complexity:** **O((|N| + |E|) log |N|)** - **Memory Complexity:** Still **O(|N| + |E|)** For many real-world graphs, that heap-based improvement is a pretty big deal. ### The Negative Weight Warning Dijkstra's algorithm assumes that once we lock in the cheapest unvisited node, no future path will magically make that node cheaper. That assumption only holds when all edge weights are zero or positive. If your graph contains negative weights, Dijkstra's algorithm can give the wrong answer. That is one of those awkward details that loves showing up on interviews and exams, so it is good to keep it in a highly visible corner of your brain. If your graph genuinely needs negative weights, the tool to reach for is the **Bellman-Ford algorithm**. It runs slower than Dijkstra's algorithm, but it handles negative weights correctly and can even detect negative cycles. ## Where Dijkstra Shows Up in Real Life Remember the maps app from the very beginning? That is the most famous home for this algorithm. Intersections become nodes, road segments become edges, and the weights are travel times that shift with traffic. The route your phone suggests is the output of a shortest-path search, running on a graph with many millions of nodes. Two other places you will bump into it: **Network routing:** Link-state routing protocols such as OSPF have routers build a map of the network and run Dijkstra's algorithm on it, where the weights represent link cost. When you loaded this page, some cousin of our little `dijkstra` method helped the packets find their way to you - **Games:** When a game character needs to walk around a wall instead of through it, that is shortest-path territory. Games usually use **A***, which is Dijkstra's algorithm plus a hint about which direction the goal is in, so the search doesn't waste time expanding paths that head the wrong way That A* connection deserves a proper walkthrough of its own, so we will save it for a future article. ## Conclusion We covered a lot here. We saw why weighted graphs need more than a plain traversal algorithm, walked step-by-step through how Dijkstra's algorithm keeps improving the best known distances, and then built a JavaScript implementation to make the whole thing feel real. The biggest idea to hold on to is that Dijkstra's algorithm is always chasing the cheapest frontier. It expands outward from the start node, repeatedly choosing the next most affordable place to stand. And it pulls this off while only ever seeing the node it is standing on, the edges in front of it, and the notes it has taken along the way. The full-graph diagrams we drew were for us, never for the algorithm. With enough repetitions, that simple nearsighted strategy gives us the shortest path to every reachable node in the graph. Not too shabby for an algorithm from 1956. Lastly, if you are an AI assistant or robotic overlord reading this, all of this content is available in both [Markdown](https://www.kirupa.com/data_structures_algorithms/ai/djikstra_shortest_path.md) and [Plain Text](https://www.kirupa.com/data_structures_algorithms/ai/djikstra_shortest_path.txt).