{"id":38,"date":"2011-08-28T19:09:03","date_gmt":"2011-08-28T19:09:03","guid":{"rendered":"http:\/\/learninglover.com\/blog\/?p=38"},"modified":"2013-11-06T21:36:35","modified_gmt":"2013-11-07T02:36:35","slug":"dijkstras-algorithm","status":"publish","type":"post","link":"https:\/\/learninglover.com\/blog\/index.php\/2011\/08\/28\/dijkstras-algorithm\/","title":{"rendered":"Dijkstra&#8217;s Algorithm"},"content":{"rendered":"<p>I&#8217;ve just written <a href=\"http:\/\/www.learninglover.com\/examples.php?id=6\">a script that executes Dijkstra&#8217;s algorithm<\/a> that seeks to find the shortest path tree on a randomly generated graph. <\/p>\n<p>Given a weighted graph <em>G<\/em> and a vertex <em>s<\/em>, the single node shortest path problem seeks to find the shortest path from <em>s<\/em> to every other vertex in this graph such that the sum of the weights of the edges along these paths is minimized. One famous algorithm for this problem is Dijkstra&#8217;s Algorithm, which constructs this shortest path tree using techniques of greedy algorithms and dynamic programming. <\/p>\n<p>Dijkstra&#8217;s Algorithm works as follows. <\/p>\n<ul>\n<li>Initially we have an empty path tree <em>T<\/em>, and assume that the distance to every vertex in the graph has some maximum cost, say infinity, i.e. <em>w<\/em>(<em>v<\/em>) = infinity for all <em>v<\/em> in <em>V<\/em>.<\/li>\n<li>Add the node <em>s<\/em> to the tree, and give the associated path cost a value of zero, i.e. <em>w<\/em>(<em>s<\/em>) = 0.<\/li>\n<li>Find the edge which is adjacent to <em>T<\/em> that adds the vertex whose cost is minimum, i.e. we look for an <em>e<\/em> = (<em>u<\/em>, <em>v<\/em>) such that <em>u<\/em> is in <em>T<\/em>, and <em>v<\/em> is not in <em>T<\/em> and <em>w<\/em>(<em>u<\/em>) + cost(<em>u<\/em>, <em>v<\/em>) &lt; <em>w<\/em>(<em>v<\/em>) is minimum. If no such edge exists go to 5.<\/li>\n<li>Add the corresponding edge and vertex to the tree, and update the weight vector of the vertex <em>v<\/em>. Go to 3.<\/li>\n<li>The path tree <em>T<\/em> now represents the shortest path from the vertex <em>s<\/em> to all other vertices reachable in the graph <em>G<\/em>. The weight vector <em>w<\/em> represents the costs of these paths. <\/li>\n<\/ul>\n<p>For an example of Dijkstra&#8217;s algorithm executed on the Graph with the following adjacency matrix: <\/p>\n<table>\n<tr>\n<td><\/td>\n<td>0<\/td>\n<td>1<\/td>\n<td>2<\/td>\n<td>3<\/td>\n<td>4<\/td>\n<td>5<\/td>\n<td>6<\/td>\n<td>7<\/td>\n<\/tr>\n<tr>\n<td>0<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>2<\/td>\n<td>4<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>20<\/td>\n<td>&#8211;<\/td>\n<\/tr>\n<tr>\n<td>1<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>11<\/td>\n<td>11<\/td>\n<td>7<\/td>\n<td>5<\/td>\n<td>&#8211;<\/td>\n<\/tr>\n<tr>\n<td>2<\/td>\n<td>2<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>10<\/td>\n<td>&#8211;<\/td>\n<td>7<\/td>\n<td>&#8211;<\/td>\n<\/tr>\n<tr>\n<td>3<\/td>\n<td>4<\/td>\n<td>11<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>2<\/td>\n<\/tr>\n<tr>\n<td>4<\/td>\n<td>&#8211;<\/td>\n<td>11<\/td>\n<td>10<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<\/tr>\n<tr>\n<td>5<\/td>\n<td>&#8211;<\/td>\n<td>7<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>14<\/td>\n<\/tr>\n<tr>\n<td>6<\/td>\n<td>20<\/td>\n<td>5<\/td>\n<td>7<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<\/tr>\n<tr>\n<td>7<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<td>2<\/td>\n<td>&#8211;<\/td>\n<td>14<\/td>\n<td>&#8211;<\/td>\n<td>&#8211;<\/td>\n<\/tr>\n<\/table>\n<p><img decoding=\"async\" src=\"http:\/\/learninglover.com\/blog\/wp-content\/gallery\/examples\/dijkstra.jpg\" alt=\"Graph with 8 Nodes\" \/><\/p>\n<p>Suppose we are interested in discovering the shortest paths from the node 0. <\/p>\n<p>Initially Dijkstra&#8217;s algorithm constructs an empty path tree, T = {}. <\/p>\n<p>Because we want to discover the shortest paths from the node 0, our first step will be to add this node to the tree and update the weight vector.<br \/>\nT = {0}<br \/>\nw(0) = 0. <\/p>\n<p>Now we will consider the edges adjacent to T, {(0, 2), (0, 3), and (0, 6)}. Our assumption is that the shortest path of every vertex in T has already been computed correctly and we will seek the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T. The edge that does that currently is (0, 2) since w(0) = 0 and c(0, 2) = 2. We add the node 2 to T and update the weight vector.<br \/>\nT = {0, 2}<br \/>\nw(2) = 2. <\/p>\n<p>The edges adjacent to T are now {(0, 3), (0, 6), (2, 4), (2, 6)}.<br \/>\nThe associated path costs are:<br \/>\nw(0) + c(0, 3) = 0 + 4 = 4<br \/>\nw(0) + c(0, 6) = 0 + 20 = 20<br \/>\nw(2) + c(2, 4) = 2 + 10 = 12<br \/>\nw(2) + c(2, 6) = 2 + 7 = 9<br \/>\nWe can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (0, 3). We add the node 3 to T and update the weight vector.<br \/>\nT = {0, 2, 3}<br \/>\nw(3) = 4<\/p>\n<p>The edges adjacent to T are now {(0, 6), (2, 4), (2, 6), (3, 1), (3, 7)}.<br \/>\nThe associated path costs are:<br \/>\nw(0) + c(0, 6) = 0 + 20 = 20<br \/>\nw(2) + c(2, 4) = 2 + 10 = 12<br \/>\nw(2) + c(2, 6) = 2 + 7 = 9<br \/>\nw(3) + c(3, 1) = 4 + 11 = 15<br \/>\nw(3) + c(3, 7) = 4 + 2 = 6<br \/>\nWe can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (3, 7). We add the node 7 to T and update the weight vector.<br \/>\nT = {0, 2, 3, 7}<br \/>\nw(7) = 6<\/p>\n<p>The edges adjacent to T are now {(0, 6), (2, 4), (2, 6), (3, 1), (5, 7)}.<br \/>\nThe associated path costs are:<br \/>\nw(0) + c(0, 6) = 0 + 20 = 20<br \/>\nw(2) + c(2, 4) = 2 + 10 = 12<br \/>\nw(2) + c(2, 6) = 2 + 7 = 9<br \/>\nw(3) + c(3, 1) = 4 + 11 = 15<br \/>\nw(7) + c(5, 7) = 6 + 14 = 20<br \/>\nWe can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (2, 6). We add the node 6 to T and update the weight vector.<br \/>\nT = {0, 2, 3, 6, 7}<br \/>\nw(6) = 9<\/p>\n<p>The edges adjacent to T are now {(2, 4), (3, 1), (5, 7) (6, 1)}.<br \/>\nThe associated path costs are:<br \/>\nw(2) + c(2, 4) = 2 + 10 = 12<br \/>\nw(3) + c(3, 1) = 4 + 11 = 15<br \/>\nw(7) + c(5, 7) = 6 + 14 = 20<br \/>\nw(6) + c(6, 1) = 9 + 5 = 14<br \/>\nWe can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (2, 4). We add the node 4 to T and update the weight vector.<br \/>\nT = {0, 2, 3, 4, 6, 7}<br \/>\nw(4) = 12<\/p>\n<p>The edges adjacent to T are now {(3, 1), (5, 7), (6, 1), (4, 1)}.<br \/>\nThe associated path costs are:<br \/>\nw(3) + c(3, 1) = 4 + 11 = 15<br \/>\nw(7) + c(5, 7) = 6 + 14 = 20<br \/>\nw(6) + c(6, 1) = 9 + 5 = 14<br \/>\nw(4) + c(4, 1) = 12 + 11 = 23<br \/>\nWe can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (6, 1). We add the node 1 to T and update the weight vector.<br \/>\nT = {0, 1, 2, 3, 4, 6, 7}<br \/>\nw(1) = 14<\/p>\n<p>The edges adjacent to T are now {(5, 7), (1, 5)}.<br \/>\nThe associated path costs are:<br \/>\nw(7) + c(5, 7) = 6 + 14 = 20<br \/>\nw(1) + c(1, 5) = 14 + 7 = 21<br \/>\nWe can see that the edge that minimizes the value w(u) + c(u, v), where u is a member of T and (u, v) is an edge adjacent to T is (5, 7). We add the node 5 to T and update the weight vector.<br \/>\nT = {0, 1, 2, 3, 4, 5, 6, 7}<br \/>\nw(5) = 20<\/p>\n<p>Now that T contains all the nodes from the tree, we know the shortest path from node 0 to all other nodes and and have solved the problem. The associated weight vector is w = [0, 14, 2, 4, 12, 20, 9, 6]. <\/p>\n<p>To learn more and see more examples, view <a href=\"http:\/\/www.learninglover.com\/examples.php?id=6\">Dijkstra&#8217;s Algorithm at LEARNINGlover.com<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>I&#8217;ve just written a script that executes Dijkstra&#8217;s algorithm that seeks to find the shortest path tree on a randomly generated graph. Given a weighted graph G and a vertex s, the single node shortest path problem seeks to find the shortest path from s to every other vertex in this graph such that the [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-38","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/posts\/38","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=38"}],"version-history":[{"count":0,"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/posts\/38\/revisions"}],"wp:attachment":[{"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=38"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=38"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/learninglover.com\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=38"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}