{"id":3662,"date":"2020-07-23T15:13:06","date_gmt":"2020-07-23T09:43:06","guid":{"rendered":"http:\/\/www.pythonpool.com\/?p=3662"},"modified":"2022-05-06T11:10:14","modified_gmt":"2022-05-06T05:40:14","slug":"dijkstras-algorithm-python","status":"publish","type":"post","link":"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/","title":{"rendered":"Implementing Dijkstra&#8217;s Algorithm in Python"},"content":{"rendered":"\n<p>Whenever we need to represent and store connections or links between elements, we use data structures known as graphs. In a graph, we have nodes (vertices) and edges. Nodes are objects (values), and edges are the lines that connect nodes. In python, we represent graphs using a<a href=\"http:\/\/www.pythonpool.com\/nested-dictionary-python\/\"> nested dictionary<\/a>. We represent nodes of the graph as the key and its connections as the value. We often need to find the shortest distance between these nodes, and we generally use Dijkstra&#8217;s Algorithm in python.&nbsp;&nbsp;A graph in general looks like this-<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" width=\"1024\" height=\"525\" src=\"http:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/3-1-1024x525.jpg\" alt=\"Dijkstra's Algorithm Python\" class=\"wp-image-3674\" srcset=\"https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/3-1-1024x525.jpg 1024w, https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/3-1-300x154.jpg 300w, https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/3-1-768x394.jpg 768w, https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/3-1.jpg 1343w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>So, Dijkstra&#8217;s Algorithm is used to find the shortest distance between the source node and the target node. The approach that Dijkstra&#8217;s Algorithm follows is known as the Greedy Approach. Although today&#8217;s point of discussion is understanding the <a href=\"http:\/\/www.pythonpool.com\/numpy-logical-_and\/\" target=\"_blank\" rel=\"noreferrer noopener\">logic and<\/a> implementation of Dijkstra&#8217;s Algorithm in python, if you are unfamiliar with terms like Greedy Approach and Graphs, bear with us for some time, and we will try explaining each and everything in this article.&nbsp;<\/p>\n\n\n\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_74 counter-hierarchy ez-toc-counter ez-toc-transparent ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #990303;color:#990303\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #990303;color:#990303\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 eztoc-toggle-hide-by-default' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/#Concept_Behind_Dijkstras_Algorithm\" >Concept Behind Dijkstra&#8217;s Algorithm&nbsp;<\/a><ul class='ez-toc-list-level-3' ><li class='ez-toc-heading-level-3'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/#What_is_Greedy_Approach\" >What is Greedy Approach?&nbsp;<\/a><\/li><\/ul><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/#Dijkstras_Algorithm_Description\" >Dijkstra&#8217;s Algorithm Description<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/#Implementing_Dijkstras_Algorithm_in_Python\" >Implementing Dijkstra&#8217;s Algorithm in Python&nbsp;<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/#Must_Read\" >Must Read<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/#Conclusion\" >Conclusion&nbsp;<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"wp-block-heading\" id=\"h-concept-behind-dijkstra-s-algorithm\"><span class=\"ez-toc-section\" id=\"Concept_Behind_Dijkstras_Algorithm\"><\/span>Concept Behind Dijkstra&#8217;s Algorithm&nbsp;<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"h-what-is-greedy-approach\"><span class=\"ez-toc-section\" id=\"What_is_Greedy_Approach\"><\/span>What is Greedy Approach?&nbsp;<span class=\"ez-toc-section-end\"><\/span><\/h3>\n\n\n\n<p>In the Introduction section, we told you that Dijkstra&#8217;s Algorithm works on the greedy approach, so what is this Greedy approach?<\/p>\n\n\n\n<p> In Laymen&#8217;s terms, the Greedy approach is the strategy in which we chose the best possible choice available, assuming that it will lead us to the best solution.&nbsp;&nbsp;<\/p>\n\n\n\n<p>Think about it in this way, we chose the best solution at that moment without thinking much about the consequences in the future.&nbsp;&nbsp;<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"h-dijkstra-s-algorithm-description\"><span class=\"ez-toc-section\" id=\"Dijkstras_Algorithm_Description\"><\/span>Dijkstra&#8217;s Algorithm Description<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p><strong>Step 1:<\/strong> Make a temporary graph that stores the original graph&#8217;s value and name it as an unvisited graph. Also, initialize a list called a path to save the shortest path between source and target.&nbsp;<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" width=\"1024\" height=\"525\" src=\"http:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/3-2-1024x525.jpg\" alt=\"Dijkstra's algorithm python\" class=\"wp-image-3675\" srcset=\"https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/3-2-1024x525.jpg 1024w, https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/3-2-300x154.jpg 300w, https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/3-2-768x394.jpg 768w, https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/3-2.jpg 1343w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p><strong>Step 2<\/strong>: We need to calculate the Minimum Distance from the source node to each node. <\/p>\n\n\n\n<p>Initially, mark total_distance for every node as infinity (\u221e) and the source node mark total_distance as 0, as the distance from the source node to the source node is 0. Also, mark this source node as current_node.&nbsp;<\/p>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img decoding=\"async\" src=\"http:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/4-1024x556.jpg\" alt=\"Dijkstra's algorithm python\" class=\"wp-image-3676\" width=\"591\" height=\"319\"\/><figcaption><strong><em>The source node\/ current_node is &#8216;A&#8217;, mark it as 0.<\/em><\/strong><\/figcaption><\/figure>\n\n\n\n<p><strong>Step 3<\/strong>: From the current_node, select the neighbor nodes (nodes that are directly connected) in any random order. Check if the current value of that node is (initially it will be (\u221e)) is higher than (the value of the current_node + value of the edge that connects this neighbor node with current_node ).<\/p>\n\n\n\n<p> If yes, then replace the importance of this neighbor node with the value of the current_node + value of the edge that connects this neighbor node with current_node. Repeat this process for all the neighboring nodes of the current node<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" width=\"1024\" height=\"581\" src=\"http:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/5-1024x581.jpg\" alt=\"Dijkstra's algorithm python\" class=\"wp-image-3677\" srcset=\"https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/5-1024x581.jpg 1024w, https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/5-300x170.jpg 300w, https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/5-768x436.jpg 768w, https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/5.jpg 1489w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><figcaption><strong>At C, as 2 &lt; \u221e, update the value of C from \u221e to 2.<\/strong><\/figcaption><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" width=\"1024\" height=\"524\" src=\"http:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/6-1024x524.jpg\" alt=\"Dijkstra's algorithm python\" class=\"wp-image-3679\" srcset=\"https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/6-1024x524.jpg 1024w, https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/6-300x153.jpg 300w, https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/6-768x393.jpg 768w, https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/6.jpg 1525w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><figcaption><strong><em>At B, as 5 &lt; \u221e, update the value of B from \u221e to 5.<\/em><\/strong><\/figcaption><\/figure>\n\n\n\n<p><strong>Step 4<\/strong>: After we have updated all the neighboring nodes of the current node&#8217;s values, it&#8217;s time to delete the current node from the unvisited_nodes. <\/p>\n\n\n\n<p>From all those nodes that were neighbors of the current node, the neighbor chose the neighbor with the minimum_distance and set it as current_node.&nbsp;<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" width=\"1024\" height=\"628\" src=\"http:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/7-1-1024x628.jpg\" alt=\"Dijkstra's algorithm python\" class=\"wp-image-3680\" srcset=\"https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/7-1-1024x628.jpg 1024w, https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/7-1-300x184.jpg 300w, https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/7-1-768x471.jpg 768w, https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/7-1.jpg 1394w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><figcaption><strong>At D (the path is A-&gt;C-&gt;D), 9 (7+2) is less than \u221e, update the value from \u221e to 9.<\/strong><\/figcaption><\/figure>\n\n\n\n<p><strong>Step 5<\/strong>: Repeat steps 3 and 4 until and unless all the nodes in unvisited_visited nodes have been visited.&nbsp;&nbsp;<\/p>\n\n\n\n<p>Once all the nodes have been visited, we will get the shortest <a href=\"https:\/\/en.wikipedia.org\/wiki\/Distance\" target=\"_blank\" aria-label=\"undefined (opens in a new tab)\" rel=\"noreferrer noopener\">distance<\/a> from the source node to the target node.&nbsp;&nbsp;<\/p>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img decoding=\"async\" src=\"http:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/8-1024x655.jpg\" alt=\"Dijkstra's algorithm python\" class=\"wp-image-3681\" width=\"588\" height=\"374\"\/><figcaption><strong><em>When we again arrive at D (this time the path is A-&gt;B -&gt;D), the value of D becomes 8.<\/em><\/strong><\/figcaption><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" width=\"1024\" height=\"648\" src=\"http:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/final-1024x648.jpg\" alt=\"Dijkstra's algorithm python\" class=\"wp-image-3691\" srcset=\"https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/final-1024x648.jpg 1024w, https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/final-300x190.jpg 300w, https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/final-768x486.jpg 768w, https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/final.jpg 1484w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><figcaption><strong><em>Finally, at E, 15 &lt;  \u221e, So the distance will update from \u221e to 15.<\/em><\/strong><\/figcaption><\/figure>\n\n\n\n<p>The output we got here is 15. <\/p>\n\n\n\n<p>Now that we have the idea of how Dijkstra&#8217;s Algorithm works let us make a python program for it and verify our output from above.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"h-implementing-dijkstra-s-algorithm-in-python\"><span class=\"ez-toc-section\" id=\"Implementing_Dijkstras_Algorithm_in_Python\"><\/span>Implementing Dijkstra&#8217;s Algorithm in Python&nbsp;<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: python; title: ; notranslate\" title=\"\">\ndef dijkstra(current, nodes, distances):\n    # These are all the nodes which have not been visited yet\n    unvisited = {node: None for node in nodes}\n    # It will store the shortest distance from one node to another\n    visited = {}\n    # It will store the predecessors of the nodes\n    currentDistance = 0\n    unvisited&#x5B;current] = currentDistance\n    # Running the loop while all the nodes have been visited\n    while True:\n        # iterating through all the unvisited node\n        for neighbour, distance in distances&#x5B;current].items():\n            # Iterating through the connected nodes of current_node (for \n            # example, a is connected with b and c having values 10 and 3\n            # respectively) and the weight of the edges\n            if neighbour not in unvisited: continue\n            newDistance = currentDistance + distance\n            if unvisited&#x5B;neighbour] is None or unvisited&#x5B;neighbour] &gt; newDistance:\n                unvisited&#x5B;neighbour] = newDistance\n        # Till now the shortest distance between the source node and target node \n        # has been found. Set the current node as the target node\n        visited&#x5B;current] = currentDistance\n        del unvisited&#x5B;current]\n        if not unvisited: break\n        candidates = &#x5B;node for node in unvisited.items() if node&#x5B;1]]\n        print(sorted(candidates, key = lambda x: x&#x5B;1]))\n        current, currentDistance = sorted(candidates, key = lambda x: x&#x5B;1])&#x5B;0]\n    return visited\n \nnodes = ('A', 'B', 'C', 'D', 'E')\ndistances = {\n    'A': {'B': 5, 'C': 2},\n    'B': {'C': 2, 'D': 3},\n    'C': {'B': 3, 'D': 7},\n    'D': {'E': 7},\n    'E': {'D': 9}}\ncurrent = 'A'\n \nprint(dijkstra(current, nodes, distances))\n<\/pre><\/div>\n\n\n<p>Output-<\/p>\n\n\n\n<pre class=\"wp-block-preformatted\">{'A': 0, 'C': 2, 'B': 5, 'D': 8, 'E': 15}<\/pre>\n\n\n\n<p>The answer is same that we got from the algorithm.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"h-must-read\"><span class=\"ez-toc-section\" id=\"Must_Read\"><\/span><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-luminous-vivid-orange-color\">Must Read<\/mark><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li><a href=\"http:\/\/www.pythonpool.com\/python-lowercase\/\">How to Convert String to Lowercase in<\/a><\/li><li><a href=\"http:\/\/www.pythonpool.com\/square-root-in-python\/\">How to Calculate Square Root<\/a><\/li><li><a href=\"http:\/\/www.pythonpool.com\/python-user-input\/\">User Input | Input () Function | Keyboard Input<\/a><\/li><li><a href=\"http:\/\/www.pythonpool.com\/python-book\/\">Best Book to Learn Python<\/a><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"h-conclusion\"><span class=\"ez-toc-section\" id=\"Conclusion\"><\/span>Conclusion&nbsp;<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>Dijkstra&#8217;s Algorithm in python comes very handily when we want to find the shortest distance between source and target. It can work for both directed and undirected graphs. The limitation of this Algorithm is that it may or may not give the correct result for negative numbers. In Google Maps, for finding the shortest route between one source to another, we use Dijkstra&#8217;s Algorithm. Another application is in networking, where it helps in sending a packet from source to destination.<\/p>\n\n\n\n<p>Try to run the programs on your side and let us know if you have any queries.<\/p>\n\n\n\n<p><strong><em>Happy Coding!<\/em><\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Whenever we need to represent and store connections or links between elements, we use data structures known as graphs. In a graph, we have nodes &#8230; <\/p>\n<p class=\"read-more-container\"><a title=\"Implementing Dijkstra&#8217;s Algorithm in Python\" class=\"read-more button\" href=\"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/#more-3662\" aria-label=\"More on Implementing Dijkstra&#8217;s Algorithm in Python\">Read more<\/a><\/p>\n","protected":false},"author":3,"featured_media":3694,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_mi_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[1654,15],"tags":[],"class_list":["post-3662","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithm","category-tutorials","infinite-scroll-item"],"yoast_head":"<!-- This site is optimized with the Yoast SEO Premium plugin v20.1 (Yoast SEO v25.0) - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Implementing Dijkstra&#039;s Algorithm in Python - Python Pool<\/title>\n<meta name=\"description\" content=\"To find the shortest distance between the source node and destination node and its path in a graph, we use Dijkstra&#039;s algorithm in python.\" \/>\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.pythonpool.com\/dijkstras-algorithm-python\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Implementing Dijkstra&#039;s Algorithm in Python\" \/>\n<meta property=\"og:description\" content=\"Whenever we need to represent and store connections or links between elements, we use data structures known as graphs. In a graph, we have nodes\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/\" \/>\n<meta property=\"og:site_name\" content=\"Python Pool\" \/>\n<meta property=\"article:published_time\" content=\"2020-07-23T09:43:06+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2022-05-06T05:40:14+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/Capture-22.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"1001\" \/>\n\t<meta property=\"og:image:height\" content=\"604\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"Ashwini Mandani\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@pythonpool\" \/>\n<meta name=\"twitter:site\" content=\"@pythonpool\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Ashwini Mandani\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"7 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/\"},\"author\":{\"name\":\"Ashwini Mandani\",\"@id\":\"https:\/\/www.pythonpool.com\/#\/schema\/person\/8a75fb48eb1f3dc952df65a8c28ac056\"},\"headline\":\"Implementing Dijkstra&#8217;s Algorithm in Python\",\"datePublished\":\"2020-07-23T09:43:06+00:00\",\"dateModified\":\"2022-05-06T05:40:14+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/\"},\"wordCount\":793,\"commentCount\":4,\"publisher\":{\"@id\":\"https:\/\/www.pythonpool.com\/#organization\"},\"image\":{\"@id\":\"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/Capture-22.jpg\",\"articleSection\":[\"Algorithm\",\"Tutorials\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/\",\"url\":\"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/\",\"name\":\"Implementing Dijkstra's Algorithm in Python - Python Pool\",\"isPartOf\":{\"@id\":\"https:\/\/www.pythonpool.com\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/Capture-22.jpg\",\"datePublished\":\"2020-07-23T09:43:06+00:00\",\"dateModified\":\"2022-05-06T05:40:14+00:00\",\"description\":\"To find the shortest distance between the source node and destination node and its path in a graph, we use Dijkstra's algorithm in python.\",\"breadcrumb\":{\"@id\":\"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/#primaryimage\",\"url\":\"https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/Capture-22.jpg\",\"contentUrl\":\"https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/Capture-22.jpg\",\"width\":1001,\"height\":604,\"caption\":\"Dijkstra's algorithm python\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/www.pythonpool.com\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Implementing Dijkstra&#8217;s Algorithm in Python\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/www.pythonpool.com\/#website\",\"url\":\"https:\/\/www.pythonpool.com\/\",\"name\":\"Python Pool\",\"description\":\"Your One-Stop Python Learning Destination\",\"publisher\":{\"@id\":\"https:\/\/www.pythonpool.com\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/www.pythonpool.com\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/www.pythonpool.com\/#organization\",\"name\":\"Python Pool\",\"url\":\"https:\/\/www.pythonpool.com\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/www.pythonpool.com\/#\/schema\/logo\/image\/\",\"url\":\"http:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/08\/aa.png\",\"contentUrl\":\"http:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/08\/aa.png\",\"width\":452,\"height\":185,\"caption\":\"Python Pool\"},\"image\":{\"@id\":\"https:\/\/www.pythonpool.com\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/x.com\/pythonpool\",\"https:\/\/www.youtube.com\/c\/pythonpool\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/www.pythonpool.com\/#\/schema\/person\/8a75fb48eb1f3dc952df65a8c28ac056\",\"name\":\"Ashwini Mandani\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/www.pythonpool.com\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/f765ed1940ac0ae1d30ce4cb2f1452c1e83143b07354d25a42c1cd118980e269?s=96&d=wavatar&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/f765ed1940ac0ae1d30ce4cb2f1452c1e83143b07354d25a42c1cd118980e269?s=96&d=wavatar&r=g\",\"caption\":\"Ashwini Mandani\"}}]}<\/script>\n<!-- \/ Yoast SEO Premium plugin. -->","yoast_head_json":{"title":"Implementing Dijkstra's Algorithm in Python - Python Pool","description":"To find the shortest distance between the source node and destination node and its path in a graph, we use Dijkstra's algorithm in python.","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.pythonpool.com\/dijkstras-algorithm-python\/","og_locale":"en_US","og_type":"article","og_title":"Implementing Dijkstra's Algorithm in Python","og_description":"Whenever we need to represent and store connections or links between elements, we use data structures known as graphs. In a graph, we have nodes","og_url":"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/","og_site_name":"Python Pool","article_published_time":"2020-07-23T09:43:06+00:00","article_modified_time":"2022-05-06T05:40:14+00:00","og_image":[{"width":1001,"height":604,"url":"https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/Capture-22.jpg","type":"image\/jpeg"}],"author":"Ashwini Mandani","twitter_card":"summary_large_image","twitter_creator":"@pythonpool","twitter_site":"@pythonpool","twitter_misc":{"Written by":"Ashwini Mandani","Est. reading time":"7 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/#article","isPartOf":{"@id":"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/"},"author":{"name":"Ashwini Mandani","@id":"https:\/\/www.pythonpool.com\/#\/schema\/person\/8a75fb48eb1f3dc952df65a8c28ac056"},"headline":"Implementing Dijkstra&#8217;s Algorithm in Python","datePublished":"2020-07-23T09:43:06+00:00","dateModified":"2022-05-06T05:40:14+00:00","mainEntityOfPage":{"@id":"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/"},"wordCount":793,"commentCount":4,"publisher":{"@id":"https:\/\/www.pythonpool.com\/#organization"},"image":{"@id":"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/#primaryimage"},"thumbnailUrl":"https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/Capture-22.jpg","articleSection":["Algorithm","Tutorials"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/","url":"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/","name":"Implementing Dijkstra's Algorithm in Python - Python Pool","isPartOf":{"@id":"https:\/\/www.pythonpool.com\/#website"},"primaryImageOfPage":{"@id":"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/#primaryimage"},"image":{"@id":"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/#primaryimage"},"thumbnailUrl":"https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/Capture-22.jpg","datePublished":"2020-07-23T09:43:06+00:00","dateModified":"2022-05-06T05:40:14+00:00","description":"To find the shortest distance between the source node and destination node and its path in a graph, we use Dijkstra's algorithm in python.","breadcrumb":{"@id":"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/#primaryimage","url":"https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/Capture-22.jpg","contentUrl":"https:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/07\/Capture-22.jpg","width":1001,"height":604,"caption":"Dijkstra's algorithm python"},{"@type":"BreadcrumbList","@id":"https:\/\/www.pythonpool.com\/dijkstras-algorithm-python\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/www.pythonpool.com\/"},{"@type":"ListItem","position":2,"name":"Implementing Dijkstra&#8217;s Algorithm in Python"}]},{"@type":"WebSite","@id":"https:\/\/www.pythonpool.com\/#website","url":"https:\/\/www.pythonpool.com\/","name":"Python Pool","description":"Your One-Stop Python Learning Destination","publisher":{"@id":"https:\/\/www.pythonpool.com\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.pythonpool.com\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/www.pythonpool.com\/#organization","name":"Python Pool","url":"https:\/\/www.pythonpool.com\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.pythonpool.com\/#\/schema\/logo\/image\/","url":"http:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/08\/aa.png","contentUrl":"http:\/\/www.pythonpool.com\/wp-content\/uploads\/2020\/08\/aa.png","width":452,"height":185,"caption":"Python Pool"},"image":{"@id":"https:\/\/www.pythonpool.com\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/x.com\/pythonpool","https:\/\/www.youtube.com\/c\/pythonpool"]},{"@type":"Person","@id":"https:\/\/www.pythonpool.com\/#\/schema\/person\/8a75fb48eb1f3dc952df65a8c28ac056","name":"Ashwini Mandani","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.pythonpool.com\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/f765ed1940ac0ae1d30ce4cb2f1452c1e83143b07354d25a42c1cd118980e269?s=96&d=wavatar&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/f765ed1940ac0ae1d30ce4cb2f1452c1e83143b07354d25a42c1cd118980e269?s=96&d=wavatar&r=g","caption":"Ashwini Mandani"}}]}},"_links":{"self":[{"href":"https:\/\/www.pythonpool.com\/wp-json\/wp\/v2\/posts\/3662","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.pythonpool.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.pythonpool.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.pythonpool.com\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/www.pythonpool.com\/wp-json\/wp\/v2\/comments?post=3662"}],"version-history":[{"count":16,"href":"https:\/\/www.pythonpool.com\/wp-json\/wp\/v2\/posts\/3662\/revisions"}],"predecessor-version":[{"id":23127,"href":"https:\/\/www.pythonpool.com\/wp-json\/wp\/v2\/posts\/3662\/revisions\/23127"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.pythonpool.com\/wp-json\/wp\/v2\/media\/3694"}],"wp:attachment":[{"href":"https:\/\/www.pythonpool.com\/wp-json\/wp\/v2\/media?parent=3662"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.pythonpool.com\/wp-json\/wp\/v2\/categories?post=3662"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.pythonpool.com\/wp-json\/wp\/v2\/tags?post=3662"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}