--- title: Dijkstra's Shortest Path Algorithm | daily.dev description: A step-by-step walkthrough of Dijkstra's shortest path algorithm on weighted graphs, explaining why BFS falls short for weighted graphs, how the relaxation... canonical: https://daily.dev/posts/dijkstra-s-shortest-path-algorithm-hrwtbxtsr twitter:card: summary_large_image twitter:site: @dailydotdev og:type: website og:site_name: daily.dev og:title: Dijkstra's Shortest Path Algorithm | daily.dev og:description: A step-by-step walkthrough of Dijkstra's shortest path algorithm on weighted graphs, explaining why BFS falls short for weighted graphs, how the relaxation... og:url: https://daily.dev/posts/dijkstra-s-shortest-path-algorithm-hrwtbxtsr og:image: https://api.daily.dev/og/posts/HrWTBxTSR.png og:image:alt: Dijkstra's Shortest Path Algorithm og:image:width: 1200 og:image:height: 630 og:locale: en --- > ## Documentation Index > Fetch the complete documentation index at: https://daily.dev/llms.txt > Use this file to discover all available pages before exploring further. # Dijkstra's Shortest Path Algorithm **[Kirupa](https://daily.dev/sources/kirupa)** · 18 min read · 28 upvotes · 3 comments ## Summary A step-by-step walkthrough of Dijkstra's shortest path algorithm on weighted graphs, explaining why BFS falls short for weighted graphs, how the relaxation process works, and how to implement it in JavaScript. Covers both a simple O(N²+E) scan-based version and an optimized heap-backed priority queue version with O((N+E)logN) complexity. Includes path reconstruction, lazy deletion, performance analysis, negative weight limitations, and real-world applications like GPS routing, network protocols (OSPF), and game pathfinding (A*). ## Full article daily.dev links to this article rather than hosting it. Read it at the original source: ## Questions this post answers ### Why does Dijkstra's algorithm fail with negative edge weights? Dijkstra's algorithm assumes that once the cheapest unvisited node is locked in, no future path can make it cheaper, and this assumption only holds when all edge weights are zero or positive. Negative weights can produce wrong shortest-path results. Bellman-Ford is the algorithm to use instead when negative weights are present, since it handles them correctly and can even detect negative cycles, though it runs slower than Dijkstra's. _Anyone weighing Dijkstra versus Bellman-Ford for a graph problem can find comparisons like this on daily.dev._ ### What is the time complexity of Dijkstra's algorithm with a min-heap priority queue versus a simple linear scan? The simple version that scans all unvisited nodes to find the smallest distance runs in O(|N|^2 + |E|) time. Replacing that scan with a min-heap-backed priority queue improves runtime to O((|N| + |E|) log |N|), while memory complexity stays at O(|N| + |E|) in both versions. For large graphs, the heap-based approach is a significant performance improvement. _Developers optimizing graph algorithms can track complexity trade-offs like these through daily.dev._ ### What is lazy deletion in a heap-based Dijkstra implementation? Lazy deletion is a technique where, instead of updating a stale entry already sitting in the priority queue, a new cheaper entry for the same node is simply inserted alongside it. When the old, more expensive entry eventually surfaces during extraction, it gets recognized as outdated via a visited check and is skipped rather than processed again. _Engineers implementing priority-queue-based algorithms can dig into patterns like lazy deletion via daily.dev._ ## Community discussion Top comments from developers on daily.dev. **@allinonetools** · 4 upvotes > I like that you covered the negative-weight limitation too. That's one detail that's easy to miss when first learning the algorithm. **@sachchidanand** · 1 upvotes > Ahh, after many years .... ## Similar posts on daily.dev - [Understanding Dijkstra's Algorithm](https://daily.dev/posts/understanding-dijkstra-s-algorithm-glnjkkhij) · freeCodeCamp · 4 upvotes · 0 comments - [Dijkstra Lab: Graph Generator and Shortest Path Visualizer](https://daily.dev/posts/dijkstra-lab-graph-generator-and-shortest-path-visualizer-rwt33f1px) · Kirupa · 1 upvotes · 0 comments - [Negative Weight Cycle – Bellman-Ford Algorithm in Java](https://daily.dev/posts/negative-weight-cycle-bellman-ford-algorithm-in-java-ggpdodmry) · C\# Corner · 0 upvotes · 0 comments - [The Math Behind Your Commute](https://daily.dev/posts/the-math-behind-your-commute-v7mh7o4ta) · The Palindrome · 3 upvotes · 0 comments --- Tags: [#javascript](https://daily.dev/tags/javascript), [#data-structures](https://daily.dev/tags/data-structures) [View this post on daily.dev](https://daily.dev/posts/dijkstra-s-shortest-path-algorithm-hrwtbxtsr) ```json {"@context":"https://schema.org","@graph":[{"@type":"Organization","@id":"https://daily.dev/#organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180},"sameAs":["https://twitter.com/dailydotdev","https://github.com/dailydotdev","https://www.linkedin.com/company/daily-dev-ltd"]},{"@type":"WebSite","@id":"https://daily.dev/#website","url":"https://daily.dev","name":"daily.dev","publisher":{"@id":"https://daily.dev/#organization"},"potentialAction":{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https://daily.dev/search?q={search_term_string}"},"query-input":"required name=search_term_string"}}]} {"@context":"https://schema.org","@type":"TechArticle","headline":"Dijkstra's Shortest Path Algorithm","url":"https://daily.dev/posts/dijkstra-s-shortest-path-algorithm-hrwtbxtsr","mainEntityOfPage":{"@type":"WebPage","@id":"https://daily.dev/posts/dijkstra-s-shortest-path-algorithm-hrwtbxtsr"},"datePublished":"2026-07-19T21:08:23.364Z","dateModified":"2026-09-14T06:51:45.662Z","description":"A step-by-step walkthrough of Dijkstra's shortest path algorithm on weighted graphs, explaining why BFS falls short for weighted graphs, how the relaxation...","image":"https://media.daily.dev/image/upload/f_auto,q_auto/v1/posts/a78c630726ddc3d22d0009f8a9385b7c?_a=AQAEuop","thumbnailUrl":"https://media.daily.dev/image/upload/f_auto,q_auto/v1/posts/a78c630726ddc3d22d0009f8a9385b7c?_a=AQAEuop","isAccessibleForFree":true,"articleSection":"Kirupa","inLanguage":"en","publisher":{"@type":"Organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180}},"author":{"@type":"Organization","name":"Kirupa","logo":"https://media.daily.dev/image/upload/t_logo,f_auto/v1/logos/ff2fdb4927d34b81bd07cd18d6049a98","url":"https://daily.dev/sources/kirupa"},"commentCount":3,"discussionUrl":"https://daily.dev/posts/dijkstra-s-shortest-path-algorithm-hrwtbxtsr","interactionStatistic":[{"@type":"InteractionCounter","interactionType":{"@type":"LikeAction"},"userInteractionCount":28},{"@type":"InteractionCounter","interactionType":{"@type":"CommentAction"},"userInteractionCount":3}],"keywords":"javascript,data-structures","timeRequired":"PT18M"} {"@context":"https://schema.org","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https://daily.dev"},{"@type":"ListItem","position":2,"name":"Kirupa","item":"https://daily.dev/sources/kirupa"},{"@type":"ListItem","position":3,"name":"Dijkstra's Shortest Path Algorithm"}]} {"@context":"https://schema.org","@type":"WebPage","@id":"https://daily.dev/posts/dijkstra-s-shortest-path-algorithm-hrwtbxtsr","comment":[{"@type":"Comment","text":"I like that you covered the negative-weight limitation too. That’s one detail that’s easy to miss when first learning the algorithm.","datePublished":"2026-07-21T03:10:41.003Z","url":"https://daily.dev/posts/HrWTBxTSR#c-Ra5vf37tn","author":{"@type":"Person","name":"AllInOneTools","url":"https://daily.dev/allinonetools","image":"https://media.daily.dev/image/upload/s--4ZT8QlF0--/f_auto/v1769790028/avatars/avatar_igzBsWloJeaegzm9bQltZ?_a=BAMAMiiu0"},"interactionStatistic":{"@type":"InteractionCounter","interactionType":{"@type":"LikeAction"},"userInteractionCount":4}},{"@type":"Comment","text":"Ahh, after many years …","datePublished":"2026-07-30T11:19:03.086Z","url":"https://daily.dev/posts/HrWTBxTSR#c-sCs8dMOxa","author":{"@type":"Person","name":"Sachchidanand Chitnis","url":"https://daily.dev/sachchidanand","image":"https://media.daily.dev/image/upload/s--QUfblGFP--/f_auto/v1782972312/avatars/avatar_1EhzrM1K8RjvlbJPwRfP6?_a=BAMAMicg0"},"interactionStatistic":{"@type":"InteractionCounter","interactionType":{"@type":"LikeAction"},"userInteractionCount":1}}]} {"@context":"https://schema.org","@type":"FAQPage","@id":"https://daily.dev/posts/dijkstra-s-shortest-path-algorithm-hrwtbxtsr#faq","mainEntity":[{"@type":"Question","name":"Why does Dijkstra's algorithm fail with negative edge weights?","acceptedAnswer":{"@type":"Answer","text":"Dijkstra's algorithm assumes that once the cheapest unvisited node is locked in, no future path can make it cheaper, and this assumption only holds when all edge weights are zero or positive. Negative weights can produce wrong shortest-path results. Bellman-Ford is the algorithm to use instead when negative weights are present, since it handles them correctly and can even detect negative cycles, though it runs slower than Dijkstra's. Anyone weighing Dijkstra versus Bellman-Ford for a graph problem can find comparisons like this on daily.dev."}},{"@type":"Question","name":"What is the time complexity of Dijkstra's algorithm with a min-heap priority queue versus a simple linear scan?","acceptedAnswer":{"@type":"Answer","text":"The simple version that scans all unvisited nodes to find the smallest distance runs in O(|N|^2 + |E|) time. Replacing that scan with a min-heap-backed priority queue improves runtime to O((|N| + |E|) log |N|), while memory complexity stays at O(|N| + |E|) in both versions. For large graphs, the heap-based approach is a significant performance improvement. Developers optimizing graph algorithms can track complexity trade-offs like these through daily.dev."}},{"@type":"Question","name":"What is lazy deletion in a heap-based Dijkstra implementation?","acceptedAnswer":{"@type":"Answer","text":"Lazy deletion is a technique where, instead of updating a stale entry already sitting in the priority queue, a new cheaper entry for the same node is simply inserted alongside it. When the old, more expensive entry eventually surfaces during extraction, it gets recognized as outdated via a visited check and is skipped rather than processed again. Engineers implementing priority-queue-based algorithms can dig into patterns like lazy deletion via daily.dev."}}]} ```