{"id":3306,"date":"2023-07-24T14:09:56","date_gmt":"2023-07-24T08:39:56","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3306"},"modified":"2023-07-24T14:09:58","modified_gmt":"2023-07-24T08:39:58","slug":"find-shortest-path-dijkstras-algorithm","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/find-shortest-path-dijkstras-algorithm\/","title":{"rendered":"Dijkstra&#8217;s Shortest Path Algorithm"},"content":{"rendered":"\n<p><\/p>\n\n\n\n<div class=\"gutentoc tocactive nostyle\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"text_open\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#approach\">Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-implementation\">C++ Code Implementation<\/a><\/li><li><a href=\"#java-code-implementation\">Java Code Implementation<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#practise-problem\">Practise Problem<\/a><\/li><li><a href=\"#faqs\">FAQs<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#q1-what-is-dijkstras-shortest-path-algorithm\">Q.1: What is Dijkstra&#8217;s Shortest Path Algorithm?<\/a><\/li><li><a href=\"#q2-how-to-implement-the-dijkstra-algorithm\">Q.2: How to Implement the Dijkstra Algorithm?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>You are given an undirected graph ( assume with N nodes and M edges)\u00a0 and each edge has some <strong>non-negative weight <\/strong>you are also given some source node S and you have to find the shortest path from starting node(vertex) S to all other nodes.<\/p>\n\n\n\n<p>Here the shortest path means the sum of the weight of edges should be minimum in that path.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<p><strong>Input:&nbsp;<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"1024\"  height=\"471\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3308 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-4.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-4.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-4-300x138.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-4-768x353.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-4-380x175.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-4-550x253.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-3-4-800x368.png 800w\" ><\/figure>\n\n\n\n<p><strong>Output:&nbsp;<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"1024\"  height=\"471\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3309 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-14.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-14.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-14-300x138.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-14-768x353.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-14-380x175.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-14-550x253.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-1-14-800x368.png 800w\" ><\/figure>\n\n\n\n<p><strong>Explanation :<\/strong><\/p>\n\n\n\n<p>0&#8211;&gt;0 : distance = 0&nbsp; Path : 0<br>0&#8211;&gt;0 : distance = 4 Path :0 2 1<br>0&#8211;&gt;0 : distance = 3 Path : 0 2<br>0&#8211;&gt;0 : distance = 6 Path : 0 2 1 3&nbsp;<br>0&#8211;&gt;0 : distance = 8 Path : 0 2 1 3 4<br>0&#8211;&gt;0 : : distance = 14 Path : 0 2 1 3 4 5<\/p>\n\n\n\n<p><strong>INPUT:&nbsp;<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"1024\"  height=\"471\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-3310 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-11.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-11.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-11-300x138.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-11-768x353.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-11-380x175.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-11-550x253.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Image-2-11-800x368.png 800w\" ><\/figure>\n\n\n\n<p><strong>OUTPUT:&nbsp;<\/strong><\/p>\n\n\n\n<p>Shortest path between 1 to 6 is 6&nbsp;<br>Path : 1 -&gt; 2 -&gt; 5 -&gt; 6<\/p>\n\n\n\n<p><strong>INTUITION:<\/strong><\/p>\n\n\n\n<p>The first thought which comes to our mind is that find all the paths and then we can compare all the paths and the path which is giving minimum cost then we will choose that path. This approach is absolutely correct but this approach to finding all the paths will increase the complexity.<\/p>\n\n\n\n<p>So to decrease the time complexity, we can take advantage of the fact that if there are multiple edges from a node to another node then we can always choose the edge which is of minimum weight. Hence if we will come to any node with less cost then we will always choose that path. And for finding the minimum edges among all the edges we can use any data structure such as a priority queue.<\/p>\n\n\n\n<p>Code: <a href=\"https:\/\/www.interviewbit.com\/tutorial\/dijkstra-algorithm\/\" target=\"_blank\" rel=\"noreferrer noopener\">Dijkstra Algorithm<\/a>&nbsp;<\/p>\n\n\n\n<h2 id=\"approach\">Approach<\/h2>\n\n\n\n<ol><li>Set the distance of the source node to 0 and initially, all the vertices are at distances at infinity.<\/li><li>Maintain the visited array so that we can maintain the status of all the vertices.<\/li><li>Now mark the current vertex as visited( which is the source node)<\/li><li>Now the vertices which are adjacent to the present vertex, update all the distance from the source vertex which is equal to the minimum of its current distance and the sum of the weight of the current edge.<\/li><li>Now the vertex which is unvisited, set one as the new current vertex and do the same thing as above to check if the node has minimum distance till now or if it is not then update it with the summation of the current node distance and current edge weight.<\/li><li>Repeat steps 3-5 until all vertices are flagged as visited.<\/li><\/ol>\n\n\n\n<h3 id=\"c-code-implementation\">C++ Code Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">bool mark[MAXN];\nvoid dijkstra(int v) {\n  fill(d, d + n, inf);\n  fill(mark, mark + n, false);\n  d[v] = 0;\n  int u;\n  priority_queue &lt; pair &lt; int, int > , vector &lt; pair &lt; int, int > > , less &lt; pair &lt; int, int > > > pq;\n  pq.push({\n    d[v],\n    v\n  });\n  while (!pq.empty()) {\n    u = pq.top().second;\n    pq.pop();\n    if (mark[u])\n      continue;\n    mark[u] = true;\n    for (auto p: adj[u]) \/\/adj[v][i] = pair(vertex, weight)\n      if (d[p.first] > d[u] + p.second) {\n        d[p.first] = d[u] + p.second;\n        pq.push({\n          d[p.first],\n          p.first\n        });\n      }\n  }\n}<\/pre>\n\n\n\n<h3 id=\"java-code-implementation\">Java Code Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public class Dijkstra {\n\n  public static void dijkstra(int[][] graph, int source) {\n    int count = graph.length;\n    boolean[] visitedVertex = new boolean[count];\n    int[] distance = new int[count];\n    for (int i = 0; i &lt; count; i++) {\n      visitedVertex[i] = false;\n      distance[i] = Integer.MAX_VALUE;\n    }\n\n    \/\/ Distance of self loop is zero\n    distance[source] = 0;\n    for (int i = 0; i &lt; count; i++) {\n\n      \/\/ Update the distance between neighbouring vertex and source vertex\n      int u = findMinDistance(distance, visitedVertex);\n      visitedVertex[u] = true;\n\n      \/\/ Update all the neighbouring vertex distances\n      for (int v = 0; v &lt; count; v++) {\n        if (!visitedVertex[v] &amp;&amp; graph[u][v] != 0 &amp;&amp; (distance[u] + graph[u][v] &lt; distance[v])) {\n          distance[v] = distance[u] + graph[u][v];\n        }\n      }\n    }\n    for (int i = 0; i &lt; distance.length; i++) {\n      System.out.println(String.format(\"Distance from %s to %s is %s\", source, i, distance[i]));\n    }\n\n  }\n\n  \/\/ Finding the minimum distance\n  private static int findMinDistance(int[] distance, boolean[] visitedVertex) {\n    int minDistance = Integer.MAX_VALUE;\n    int minDistanceVertex = -1;\n    for (int i = 0; i &lt; distance.length; i++) {\n      if (!visitedVertex[i] &amp;&amp; distance[i] &lt; minDistance) {\n        minDistance = distance[i];\n        minDistanceVertex = i;\n      }\n    }\n    return minDistanceVertex;\n  }\n}<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def dijkstra(self, times: List[List[int]], N: int, K: int) -> int:\n    graph = collections.defaultdict(list)\n    for (u, v, w) in times:\n        graph[u].append((v, w))\n\n    priority_queue = [(0, K)]\n    shortest_path = {}\n    while priority_queue:\n        w, v = heapq.heappop(priority_queue)\n        if v not in shortest_path:\n            shortest_path[v] = w\n            for v_i, w_i in graph[v]:\n                heapq.heappush(priority_queue, (w + w_i, v_i))\n\n    if len(shortest_path) == N:\n        return max(shortest_path.values())\n    else:\n        return -1<\/pre>\n\n\n\n<p><strong>Time Complexity<\/strong>: O(ELogV) where E is the number of edges and V is the number of vertices.<br><strong>Space Complexity:<\/strong> O(V)<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"practise-problem\">Practise Problem<\/h2>\n\n\n\n<ul><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/delete-edge\/\" target=\"_blank\">Delete Edge<\/a><\/li><\/ul>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<h3 id=\"q1-what-is-dijkstras-shortest-path-algorithm\"><span id=\"q-1-what-is-dijkstras-shortest-path-algorithm\">Q.1: What is Dijkstra&#8217;s Shortest Path Algorithm?<\/span><\/h3>\n\n\n\n<p><strong>Ans:<\/strong> From this Algorithm, we can find the shortest path from any source node to all other nodes.<\/p>\n\n\n\n<h3 id=\"q2-how-to-implement-the-dijkstra-algorithm\"><span id=\"q-2-how-to-implement-the-dijkstra-algorithm\">Q.2: How to Implement the Dijkstra Algorithm?<\/span><\/h3>\n\n\n\n<p><strong>Ans:<\/strong> We can implement this algorithm by using a priority queue or any STL which is capable of finding the minimum element from the array in log n and the array is changing each second.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement You are given an undirected graph ( assume with N nodes and M edges)\u00a0 and each&hellip;\n","protected":false},"author":5,"featured_media":3312,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[520,519],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3306"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=3306"}],"version-history":[{"count":5,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3306\/revisions"}],"predecessor-version":[{"id":21866,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3306\/revisions\/21866"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3312"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3306"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3306"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3306"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}