{"id":2099,"date":"2024-07-10T20:25:40","date_gmt":"2024-07-10T20:25:40","guid":{"rendered":"https:\/\/www.w3computing.com\/articles\/?p=2099"},"modified":"2024-07-10T20:35:48","modified_gmt":"2024-07-10T20:35:48","slug":"how-to-implement-dijkstras-algorithm-in-cpp","status":"publish","type":"post","link":"https:\/\/www.w3computing.com\/articles\/how-to-implement-dijkstras-algorithm-in-cpp\/","title":{"rendered":"How to Implement Dijkstra&#8217;s Algorithm in C++"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">Dijkstra&#8217;s Algorithm is one of the fundamental algorithms in graph theory, used to find the shortest paths from a source vertex to all other vertices in a graph with non-negative weights. In this comprehensive tutorial, we will walk through the implementation of Dijkstra&#8217;s Algorithm in C++. This tutorial is aimed at readers who have a solid understanding of C++ and basic data structures such as arrays, vectors, and priority queues.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">1. Introduction to Dijkstra&#8217;s Algorithm<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Dijkstra&#8217;s Algorithm, named after its creator Edsger Dijkstra, is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It works by maintaining a set of nodes whose shortest distance from the source is known and repeatedly selecting the node with the smallest known distance, updating the paths to its neighbors.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">2. Graph Representation<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">In C++, a graph can be represented in multiple ways. The most common representations are:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Adjacency Matrix:<\/strong> A 2D array where the cell at row i and column j represents the weight of the edge from node i to node j.<\/li>\n\n\n\n<li><strong>Adjacency List:<\/strong> An array of lists. The index of the array represents the node, and the list at each index contains pairs representing neighboring nodes and the weight of the edge connecting them.<\/li>\n<\/ul>\n\n\n\n<p class=\"wp-block-paragraph\">For Dijkstra&#8217;s Algorithm, an adjacency list is more efficient in terms of space and time complexity when dealing with sparse graphs.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">3. Priority Queue and Min-Heap<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">A priority queue is a data structure where each element has a priority. Elements with higher priority are served before elements with lower priority. In the context of Dijkstra&#8217;s Algorithm, we use a priority queue to efficiently fetch the next node with the smallest tentative distance.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">C++ provides the <code>std::priority_queue<\/code> in the Standard Library, which is implemented as a max-heap by default. For Dijkstra&#8217;s Algorithm, we need a min-heap, which can be achieved by using a custom comparator or by using <code>std::greater<\/code>.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">4. Implementation Details<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Before we dive into the code, let&#8217;s outline the steps involved in Dijkstra&#8217;s Algorithm:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Initialize Distances:<\/strong> Set the distance to the source node to 0 and all other nodes to infinity.<\/li>\n\n\n\n<li><strong>Initialize Priority Queue:<\/strong> Push the source node with distance 0 into the priority queue.<\/li>\n\n\n\n<li><strong>Process Nodes:<\/strong> While the priority queue is not empty, pop the node with the smallest distance. For each neighbor of this node, calculate the tentative distance through this node. If this distance is smaller than the previously known distance, update the distance and push the neighbor into the priority queue.<\/li>\n<\/ol>\n\n\n\n<h2 class=\"wp-block-heading\">5. Step-by-Step Implementation<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">Let&#8217;s implement Dijkstra&#8217;s Algorithm step by step.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">5.1 Include Necessary Headers<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">We start by including the necessary headers for our implementation.<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-1\" data-shcb-language-name=\"HTML, XML\" data-shcb-language-slug=\"xml\"><span><code class=\"hljs language-xml\">#include <span class=\"hljs-tag\">&lt;<span class=\"hljs-name\">iostream<\/span>&gt;<\/span>\n#include <span class=\"hljs-tag\">&lt;<span class=\"hljs-name\">vector<\/span>&gt;<\/span>\n#include <span class=\"hljs-tag\">&lt;<span class=\"hljs-name\">queue<\/span>&gt;<\/span>\n#include <span class=\"hljs-tag\">&lt;<span class=\"hljs-name\">limits<\/span>&gt;<\/span><\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-1\"><span class=\"shcb-language__label\">Code language:<\/span> <span class=\"shcb-language__name\">HTML, XML<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">xml<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<h3 class=\"wp-block-heading\">5.2 Define the Graph Structure<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Next, we define the graph structure using an adjacency list.<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-2\" data-shcb-language-name=\"PHP\" data-shcb-language-slug=\"php\"><span><code class=\"hljs language-php\">typedef std::pair&lt;int, int&gt; Edge; <span class=\"hljs-comment\">\/\/ (weight, destination)<\/span>\ntypedef std::vector&lt;std::vector&lt;Edge&gt;&gt; Graph;<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-2\"><span class=\"shcb-language__label\">Code language:<\/span> <span class=\"shcb-language__name\">PHP<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">php<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<h3 class=\"wp-block-heading\">5.3 Dijkstra&#8217;s Algorithm Function<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Now, let&#8217;s write the Dijkstra function.<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-3\" data-shcb-language-name=\"PHP\" data-shcb-language-slug=\"php\"><span><code class=\"hljs language-php\">std::vector&lt;int&gt; dijkstra(<span class=\"hljs-keyword\">const<\/span> Graph&amp; graph, int source) {\n    int n = graph.size();\n    std::vector&lt;int&gt; dist(n, std::numeric_limits&lt;int&gt;::max());\n    dist&#91;source] = <span class=\"hljs-number\">0<\/span>;\n\n    std::priority_queue&lt;Edge, std::vector&lt;Edge&gt;, std::greater&lt;Edge&gt;&gt; pq;\n    pq.push({<span class=\"hljs-number\">0<\/span>, source});\n\n    <span class=\"hljs-keyword\">while<\/span> (!pq.<span class=\"hljs-keyword\">empty<\/span>()) {\n        int u = pq.top().second;\n        pq.pop();\n\n        <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">const<\/span> auto&amp; edge : graph&#91;u]) {\n            int v = edge.second;\n            int weight = edge.first;\n\n            <span class=\"hljs-keyword\">if<\/span> (dist&#91;u] + weight &lt; dist&#91;v]) {\n                dist&#91;v] = dist&#91;u] + weight;\n                pq.push({dist&#91;v], v});\n            }\n        }\n    }\n\n    <span class=\"hljs-keyword\">return<\/span> dist;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-3\"><span class=\"shcb-language__label\">Code language:<\/span> <span class=\"shcb-language__name\">PHP<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">php<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<h3 class=\"wp-block-heading\">5.4 Main Function<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Let&#8217;s create a main function to test our implementation.<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-4\" data-shcb-language-name=\"PHP\" data-shcb-language-slug=\"php\"><span><code class=\"hljs language-php\">int main() {\n    int n = <span class=\"hljs-number\">5<\/span>; <span class=\"hljs-comment\">\/\/ Number of nodes<\/span>\n    Graph graph(n);\n\n    <span class=\"hljs-comment\">\/\/ Add edges<\/span>\n    graph&#91;<span class=\"hljs-number\">0<\/span>].push_back({<span class=\"hljs-number\">10<\/span>, <span class=\"hljs-number\">1<\/span>});\n    graph&#91;<span class=\"hljs-number\">0<\/span>].push_back({<span class=\"hljs-number\">3<\/span>, <span class=\"hljs-number\">2<\/span>});\n    graph&#91;<span class=\"hljs-number\">1<\/span>].push_back({<span class=\"hljs-number\">1<\/span>, <span class=\"hljs-number\">2<\/span>});\n    graph&#91;<span class=\"hljs-number\">1<\/span>].push_back({<span class=\"hljs-number\">2<\/span>, <span class=\"hljs-number\">3<\/span>});\n    graph&#91;<span class=\"hljs-number\">2<\/span>].push_back({<span class=\"hljs-number\">4<\/span>, <span class=\"hljs-number\">1<\/span>});\n    graph&#91;<span class=\"hljs-number\">2<\/span>].push_back({<span class=\"hljs-number\">8<\/span>, <span class=\"hljs-number\">3<\/span>});\n    graph&#91;<span class=\"hljs-number\">2<\/span>].push_back({<span class=\"hljs-number\">2<\/span>, <span class=\"hljs-number\">4<\/span>});\n    graph&#91;<span class=\"hljs-number\">3<\/span>].push_back({<span class=\"hljs-number\">7<\/span>, <span class=\"hljs-number\">4<\/span>});\n    graph&#91;<span class=\"hljs-number\">4<\/span>].push_back({<span class=\"hljs-number\">9<\/span>, <span class=\"hljs-number\">3<\/span>});\n\n    std::vector&lt;int&gt; distances = dijkstra(graph, <span class=\"hljs-number\">0<\/span>);\n\n    std::cout &lt;&lt; <span class=\"hljs-string\">\"Distances from source 0:\\n\"<\/span>;\n    <span class=\"hljs-keyword\">for<\/span> (int i = <span class=\"hljs-number\">0<\/span>; i &lt; distances.size(); ++i) {\n        std::cout &lt;&lt; <span class=\"hljs-string\">\"Node \"<\/span> &lt;&lt; i &lt;&lt; <span class=\"hljs-string\">\": \"<\/span> &lt;&lt; distances&#91;i] &lt;&lt; <span class=\"hljs-string\">\"\\n\"<\/span>;\n    }\n\n    <span class=\"hljs-keyword\">return<\/span> <span class=\"hljs-number\">0<\/span>;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-4\"><span class=\"shcb-language__label\">Code language:<\/span> <span class=\"shcb-language__name\">PHP<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">php<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<h2 class=\"wp-block-heading\">6. Optimizations and Enhancements<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">6.1 Decreasing Key Operation<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">One potential optimization is to improve the efficiency of updating the distance values in the priority queue. While the standard priority queue in C++ does not support a decrease-key operation, we can achieve this by inserting a new pair with the updated distance into the priority queue. This might result in duplicate nodes in the queue, but they will eventually be ignored since they will not yield a shorter path.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">6.2 Handling Large Graphs<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">When dealing with very large graphs, memory usage becomes a concern. Using a more memory-efficient graph representation or an external memory algorithm might be necessary.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">6.3 Edge Case Handling<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Ensure the algorithm handles edge cases, such as graphs with:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Disconnected components.<\/li>\n\n\n\n<li>No edges.<\/li>\n\n\n\n<li>Multiple edges between the same pair of nodes.<\/li>\n\n\n\n<li>Nodes with no outgoing edges.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">7. Testing and Validation<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">7.1 Unit Tests<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Creating unit tests for the algorithm ensures that it works correctly in different scenarios.<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-5\" data-shcb-language-name=\"C++\" data-shcb-language-slug=\"cpp\"><span><code class=\"hljs language-cpp\"><span class=\"hljs-function\"><span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">test_dijkstra<\/span><span class=\"hljs-params\">()<\/span> <\/span>{\n    {\n        <span class=\"hljs-function\">Graph <span class=\"hljs-title\">graph<\/span><span class=\"hljs-params\">(<span class=\"hljs-number\">5<\/span>)<\/span><\/span>;\n        graph&#91;<span class=\"hljs-number\">0<\/span>].push_back({<span class=\"hljs-number\">10<\/span>, <span class=\"hljs-number\">1<\/span>});\n        graph&#91;<span class=\"hljs-number\">0<\/span>].push_back({<span class=\"hljs-number\">3<\/span>, <span class=\"hljs-number\">2<\/span>});\n        graph&#91;<span class=\"hljs-number\">1<\/span>].push_back({<span class=\"hljs-number\">1<\/span>, <span class=\"hljs-number\">2<\/span>});\n        graph&#91;<span class=\"hljs-number\">1<\/span>].push_back({<span class=\"hljs-number\">2<\/span>, <span class=\"hljs-number\">3<\/span>});\n        graph&#91;<span class=\"hljs-number\">2<\/span>].push_back({<span class=\"hljs-number\">4<\/span>, <span class=\"hljs-number\">1<\/span>});\n        graph&#91;<span class=\"hljs-number\">2<\/span>].push_back({<span class=\"hljs-number\">8<\/span>, <span class=\"hljs-number\">3<\/span>});\n        graph&#91;<span class=\"hljs-number\">2<\/span>].push_back({<span class=\"hljs-number\">2<\/span>, <span class=\"hljs-number\">4<\/span>});\n        graph&#91;<span class=\"hljs-number\">3<\/span>].push_back({<span class=\"hljs-number\">7<\/span>, <span class=\"hljs-number\">4<\/span>});\n        graph&#91;<span class=\"hljs-number\">4<\/span>].push_back({<span class=\"hljs-number\">9<\/span>, <span class=\"hljs-number\">3<\/span>});\n\n        <span class=\"hljs-built_in\">std<\/span>::<span class=\"hljs-built_in\">vector<\/span>&lt;<span class=\"hljs-keyword\">int<\/span>&gt; distances = dijkstra(graph, <span class=\"hljs-number\">0<\/span>);\n        assert(distances == <span class=\"hljs-built_in\">std<\/span>::<span class=\"hljs-built_in\">vector<\/span>&lt;<span class=\"hljs-keyword\">int<\/span>&gt;({<span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">7<\/span>, <span class=\"hljs-number\">3<\/span>, <span class=\"hljs-number\">9<\/span>, <span class=\"hljs-number\">5<\/span>}));\n    }\n\n    {\n        <span class=\"hljs-function\">Graph <span class=\"hljs-title\">graph<\/span><span class=\"hljs-params\">(<span class=\"hljs-number\">3<\/span>)<\/span><\/span>;\n        graph&#91;<span class=\"hljs-number\">0<\/span>].push_back({<span class=\"hljs-number\">1<\/span>, <span class=\"hljs-number\">1<\/span>});\n        graph&#91;<span class=\"hljs-number\">1<\/span>].push_back({<span class=\"hljs-number\">1<\/span>, <span class=\"hljs-number\">2<\/span>});\n\n        <span class=\"hljs-built_in\">std<\/span>::<span class=\"hljs-built_in\">vector<\/span>&lt;<span class=\"hljs-keyword\">int<\/span>&gt; distances = dijkstra(graph, <span class=\"hljs-number\">0<\/span>);\n        assert(distances == <span class=\"hljs-built_in\">std<\/span>::<span class=\"hljs-built_in\">vector<\/span>&lt;<span class=\"hljs-keyword\">int<\/span>&gt;({<span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">1<\/span>, <span class=\"hljs-number\">2<\/span>}));\n    }\n\n    {\n        <span class=\"hljs-function\">Graph <span class=\"hljs-title\">graph<\/span><span class=\"hljs-params\">(<span class=\"hljs-number\">2<\/span>)<\/span><\/span>;\n        graph&#91;<span class=\"hljs-number\">0<\/span>].push_back({<span class=\"hljs-number\">5<\/span>, <span class=\"hljs-number\">1<\/span>});\n\n        <span class=\"hljs-built_in\">std<\/span>::<span class=\"hljs-built_in\">vector<\/span>&lt;<span class=\"hljs-keyword\">int<\/span>&gt; distances = dijkstra(graph, <span class=\"hljs-number\">0<\/span>);\n        assert(distances == <span class=\"hljs-built_in\">std<\/span>::<span class=\"hljs-built_in\">vector<\/span>&lt;<span class=\"hljs-keyword\">int<\/span>&gt;({<span class=\"hljs-number\">0<\/span>, <span class=\"hljs-number\">5<\/span>}));\n    }\n\n    <span class=\"hljs-built_in\">std<\/span>::<span class=\"hljs-built_in\">cout<\/span> &lt;&lt; <span class=\"hljs-string\">\"All tests passed!\\n\"<\/span>;\n}\n\n<span class=\"hljs-function\"><span class=\"hljs-keyword\">int<\/span> <span class=\"hljs-title\">main<\/span><span class=\"hljs-params\">()<\/span> <\/span>{\n    test_dijkstra();\n    <span class=\"hljs-keyword\">return<\/span> <span class=\"hljs-number\">0<\/span>;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-5\"><span class=\"shcb-language__label\">Code language:<\/span> <span class=\"shcb-language__name\">C++<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">cpp<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<h3 class=\"wp-block-heading\">7.2 Benchmarking<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">Benchmarking the algorithm with large graphs can help understand its performance characteristics.<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-6\" data-shcb-language-name=\"C++\" data-shcb-language-slug=\"cpp\"><span><code class=\"hljs language-cpp\"><span class=\"hljs-meta\">#<span class=\"hljs-meta-keyword\">include<\/span> <span class=\"hljs-meta-string\">&lt;chrono&gt;<\/span><\/span>\n\n<span class=\"hljs-function\"><span class=\"hljs-keyword\">void<\/span> <span class=\"hljs-title\">benchmark<\/span><span class=\"hljs-params\">()<\/span> <\/span>{\n    <span class=\"hljs-keyword\">int<\/span> n = <span class=\"hljs-number\">10000<\/span>;\n    <span class=\"hljs-function\">Graph <span class=\"hljs-title\">graph<\/span><span class=\"hljs-params\">(n)<\/span><\/span>;\n\n    <span class=\"hljs-comment\">\/\/ Randomly generate edges<\/span>\n    <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> i = <span class=\"hljs-number\">0<\/span>; i &lt; n; ++i) {\n        <span class=\"hljs-keyword\">for<\/span> (<span class=\"hljs-keyword\">int<\/span> j = <span class=\"hljs-number\">0<\/span>; j &lt; <span class=\"hljs-number\">10<\/span>; ++j) {\n            <span class=\"hljs-keyword\">int<\/span> neighbor = rand() % n;\n            <span class=\"hljs-keyword\">int<\/span> weight = rand() % <span class=\"hljs-number\">100<\/span> + <span class=\"hljs-number\">1<\/span>;\n            graph&#91;i].push_back({weight, neighbor});\n        }\n    }\n\n    <span class=\"hljs-keyword\">auto<\/span> start = <span class=\"hljs-built_in\">std<\/span>::chrono::high_resolution_clock::now();\n    <span class=\"hljs-built_in\">std<\/span>::<span class=\"hljs-built_in\">vector<\/span>&lt;<span class=\"hljs-keyword\">int<\/span>&gt; distances = dijkstra(graph, <span class=\"hljs-number\">0<\/span>);\n    <span class=\"hljs-keyword\">auto<\/span> end = <span class=\"hljs-built_in\">std<\/span>::chrono::high_resolution_clock::now();\n\n    <span class=\"hljs-built_in\">std<\/span>::chrono::duration&lt;<span class=\"hljs-keyword\">double<\/span>&gt; duration = end - start;\n    <span class=\"hljs-built_in\">std<\/span>::<span class=\"hljs-built_in\">cout<\/span> &lt;&lt; <span class=\"hljs-string\">\"Benchmark completed in \"<\/span> &lt;&lt; duration.count() &lt;&lt; <span class=\"hljs-string\">\" seconds.\\n\"<\/span>;\n}\n\n<span class=\"hljs-function\"><span class=\"hljs-keyword\">int<\/span> <span class=\"hljs-title\">main<\/span><span class=\"hljs-params\">()<\/span> <\/span>{\n    benchmark();\n    <span class=\"hljs-keyword\">return<\/span> <span class=\"hljs-number\">0<\/span>;\n}<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-6\"><span class=\"shcb-language__label\">Code language:<\/span> <span class=\"shcb-language__name\">C++<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">cpp<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<h2 class=\"wp-block-heading\">8. Conclusion<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">In this tutorial, we have covered the implementation of Dijkstra&#8217;s Algorithm in C++. We started with a brief introduction to the algorithm, followed by a discussion on graph representation, priority queues, and the detailed implementation steps. We then explored optimizations, edge cases, testing, and benchmarking.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">By following this guide, you should now have a solid understanding of how to implement Dijkstra&#8217;s Algorithm in C++ and how to test and optimize it for various scenarios. This knowledge is fundamental for tackling more complex graph-related problems and algorithms.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Dijkstra&#8217;s Algorithm is one of the fundamental algorithms in graph theory, used to find the shortest paths from a source vertex to all other vertices in a graph with non-negative weights. In this comprehensive tutorial, we will walk through the implementation of Dijkstra&#8217;s Algorithm in C++. This tutorial is aimed at readers who have a [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_genesis_hide_title":false,"_genesis_hide_breadcrumbs":false,"_genesis_hide_singular_image":false,"_genesis_hide_footer_widgets":false,"_genesis_custom_body_class":"","_genesis_custom_post_class":"","_genesis_layout":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_post_was_ever_published":false},"categories":[9,4],"tags":[],"class_list":["post-2099","post","type-post","status-publish","format-standard","category-cplusplus","category-programming-languages","entry"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.9 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>How to Implement Dijkstra&#039;s Algorithm in C++<\/title>\n<meta name=\"description\" content=\"Dijkstra&#039;s Algorithm is one of the fundamental algorithms in graph theory, used to find the shortest paths from a source vertex to all other vertices\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.w3computing.com\/articles\/how-to-implement-dijkstras-algorithm-in-cpp\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"How to Implement Dijkstra&#039;s Algorithm in C++\" \/>\n<meta property=\"og:description\" content=\"Dijkstra&#039;s Algorithm is one of the fundamental algorithms in graph theory, used to find the shortest paths from a source vertex to all other vertices\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.w3computing.com\/articles\/how-to-implement-dijkstras-algorithm-in-cpp\/\" \/>\n<meta property=\"article:published_time\" content=\"2024-07-10T20:25:40+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2024-07-10T20:35:48+00:00\" \/>\n<meta name=\"author\" content=\"w3compadmin\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"w3compadmin\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"4 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"TechArticle\",\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/how-to-implement-dijkstras-algorithm-in-cpp\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/how-to-implement-dijkstras-algorithm-in-cpp\\\/\"},\"author\":{\"name\":\"w3compadmin\",\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/#\\\/schema\\\/person\\\/a550b3e20d78bb4f79b7c6b7b53f0561\"},\"headline\":\"How to Implement Dijkstra&#8217;s Algorithm in C++\",\"datePublished\":\"2024-07-10T20:25:40+00:00\",\"dateModified\":\"2024-07-10T20:35:48+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/how-to-implement-dijkstras-algorithm-in-cpp\\\/\"},\"wordCount\":743,\"articleSection\":[\"C++\",\"Programming Languages\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/how-to-implement-dijkstras-algorithm-in-cpp\\\/\",\"url\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/how-to-implement-dijkstras-algorithm-in-cpp\\\/\",\"name\":\"How to Implement Dijkstra's Algorithm in C++\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/#website\"},\"datePublished\":\"2024-07-10T20:25:40+00:00\",\"dateModified\":\"2024-07-10T20:35:48+00:00\",\"author\":{\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/#\\\/schema\\\/person\\\/a550b3e20d78bb4f79b7c6b7b53f0561\"},\"description\":\"Dijkstra's Algorithm is one of the fundamental algorithms in graph theory, used to find the shortest paths from a source vertex to all other vertices\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/how-to-implement-dijkstras-algorithm-in-cpp\\\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/how-to-implement-dijkstras-algorithm-in-cpp\\\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/how-to-implement-dijkstras-algorithm-in-cpp\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Articles Home\",\"item\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Programming Languages\",\"item\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/programming-languages\\\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"How to Implement Dijkstra&#8217;s Algorithm in C++\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/#website\",\"url\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/\",\"name\":\"Developer Articles Hub\",\"description\":\"\",\"alternateName\":\"Developer Articles\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/#\\\/schema\\\/person\\\/a550b3e20d78bb4f79b7c6b7b53f0561\",\"name\":\"w3compadmin\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/wp-content\\\/litespeed\\\/avatar\\\/bd481d404e42caa2763662a3bfe825f8.jpg?ver=1783167470\",\"url\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/wp-content\\\/litespeed\\\/avatar\\\/bd481d404e42caa2763662a3bfe825f8.jpg?ver=1783167470\",\"contentUrl\":\"https:\\\/\\\/www.w3computing.com\\\/articles\\\/wp-content\\\/litespeed\\\/avatar\\\/bd481d404e42caa2763662a3bfe825f8.jpg?ver=1783167470\",\"caption\":\"w3compadmin\"},\"sameAs\":[\"http:\\\/\\\/w3computing.com\\\/articles\"]}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"How to Implement Dijkstra's Algorithm in C++","description":"Dijkstra's Algorithm is one of the fundamental algorithms in graph theory, used to find the shortest paths from a source vertex to all other vertices","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.w3computing.com\/articles\/how-to-implement-dijkstras-algorithm-in-cpp\/","og_locale":"en_US","og_type":"article","og_title":"How to Implement Dijkstra's Algorithm in C++","og_description":"Dijkstra's Algorithm is one of the fundamental algorithms in graph theory, used to find the shortest paths from a source vertex to all other vertices","og_url":"https:\/\/www.w3computing.com\/articles\/how-to-implement-dijkstras-algorithm-in-cpp\/","article_published_time":"2024-07-10T20:25:40+00:00","article_modified_time":"2024-07-10T20:35:48+00:00","author":"w3compadmin","twitter_card":"summary_large_image","twitter_misc":{"Written by":"w3compadmin","Est. reading time":"4 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"TechArticle","@id":"https:\/\/www.w3computing.com\/articles\/how-to-implement-dijkstras-algorithm-in-cpp\/#article","isPartOf":{"@id":"https:\/\/www.w3computing.com\/articles\/how-to-implement-dijkstras-algorithm-in-cpp\/"},"author":{"name":"w3compadmin","@id":"https:\/\/www.w3computing.com\/articles\/#\/schema\/person\/a550b3e20d78bb4f79b7c6b7b53f0561"},"headline":"How to Implement Dijkstra&#8217;s Algorithm in C++","datePublished":"2024-07-10T20:25:40+00:00","dateModified":"2024-07-10T20:35:48+00:00","mainEntityOfPage":{"@id":"https:\/\/www.w3computing.com\/articles\/how-to-implement-dijkstras-algorithm-in-cpp\/"},"wordCount":743,"articleSection":["C++","Programming Languages"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/www.w3computing.com\/articles\/how-to-implement-dijkstras-algorithm-in-cpp\/","url":"https:\/\/www.w3computing.com\/articles\/how-to-implement-dijkstras-algorithm-in-cpp\/","name":"How to Implement Dijkstra's Algorithm in C++","isPartOf":{"@id":"https:\/\/www.w3computing.com\/articles\/#website"},"datePublished":"2024-07-10T20:25:40+00:00","dateModified":"2024-07-10T20:35:48+00:00","author":{"@id":"https:\/\/www.w3computing.com\/articles\/#\/schema\/person\/a550b3e20d78bb4f79b7c6b7b53f0561"},"description":"Dijkstra's Algorithm is one of the fundamental algorithms in graph theory, used to find the shortest paths from a source vertex to all other vertices","breadcrumb":{"@id":"https:\/\/www.w3computing.com\/articles\/how-to-implement-dijkstras-algorithm-in-cpp\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.w3computing.com\/articles\/how-to-implement-dijkstras-algorithm-in-cpp\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.w3computing.com\/articles\/how-to-implement-dijkstras-algorithm-in-cpp\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Articles Home","item":"https:\/\/www.w3computing.com\/articles\/"},{"@type":"ListItem","position":2,"name":"Programming Languages","item":"https:\/\/www.w3computing.com\/articles\/programming-languages\/"},{"@type":"ListItem","position":3,"name":"How to Implement Dijkstra&#8217;s Algorithm in C++"}]},{"@type":"WebSite","@id":"https:\/\/www.w3computing.com\/articles\/#website","url":"https:\/\/www.w3computing.com\/articles\/","name":"Developer Articles Hub","description":"","alternateName":"Developer Articles","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.w3computing.com\/articles\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/www.w3computing.com\/articles\/#\/schema\/person\/a550b3e20d78bb4f79b7c6b7b53f0561","name":"w3compadmin","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.w3computing.com\/articles\/wp-content\/litespeed\/avatar\/bd481d404e42caa2763662a3bfe825f8.jpg?ver=1783167470","url":"https:\/\/www.w3computing.com\/articles\/wp-content\/litespeed\/avatar\/bd481d404e42caa2763662a3bfe825f8.jpg?ver=1783167470","contentUrl":"https:\/\/www.w3computing.com\/articles\/wp-content\/litespeed\/avatar\/bd481d404e42caa2763662a3bfe825f8.jpg?ver=1783167470","caption":"w3compadmin"},"sameAs":["http:\/\/w3computing.com\/articles"]}]}},"featured_image_src":null,"featured_image_src_square":null,"author_info":{"display_name":"w3compadmin","author_link":"https:\/\/www.w3computing.com\/articles\/author\/w3compadmin\/"},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/posts\/2099","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/comments?post=2099"}],"version-history":[{"count":1,"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/posts\/2099\/revisions"}],"predecessor-version":[{"id":2100,"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/posts\/2099\/revisions\/2100"}],"wp:attachment":[{"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/media?parent=2099"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/categories?post=2099"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.w3computing.com\/articles\/wp-json\/wp\/v2\/tags?post=2099"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}