{"id":26687,"date":"2017-12-22T20:28:19","date_gmt":"2017-12-22T14:58:19","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26687"},"modified":"2017-12-22T20:28:19","modified_gmt":"2017-12-22T14:58:19","slug":"shortest-path-directed-acyclic-graph","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/shortest-path-directed-acyclic-graph\/","title":{"rendered":"Python Algorithm-Shortest Path-Shortest Path in Directed Acyclic Graph"},"content":{"rendered":"

Given a Weighted Directed Acyclic Graph and a source vertex in the graph, find the shortest paths from given source to all other vertices.<\/span>
\nFor a general weighted graph, we can calculate single source shortest distances in O(VE) time using Bellman\u2013Ford Algorithm<\/a>. For a graph with no negative weights, we can do better and calculate single source shortest distances in O(E + VLogV) time using Dijkstra\u2019s algorithm<\/a>. Can we do even better for Directed Acyclic Graph (DAG)? We can calculate single source shortest distances in O(V+E) time for DAGs. The idea is to use Topological Sorting<\/a>.<\/p>\n

We initialize distances to all vertices as infinite and distance to source as 0, then we find a topological sorting of the graph. Topological Sorting<\/a> of a graph represents a linear ordering of the graph (See below, figure (b) is a linear representation of figure (a) ). Once we have topological order (or linear representation), we one by one process all vertices in topological order. For every vertex being processed, we update distances of its adjacent using distance of current vertex.<\/p>\n[ad type=\u201dbanner\u201d]\n

Following figure is taken from this <\/a>source. It shows step by step process of finding shortest paths.<\/p>\n

\"ShortestFollowing is complete algorithm for finding shortest distances.<\/strong>
\n1)<\/strong> Initialize dist[] = {INF, INF, \u2026.} and dist[s] = 0 where s is the source vertex.
\n2)<\/strong> Create a toplogical order of all vertices.
\n3) <\/strong>Do following for every vertex u in topological order.
\nDo following for every adjacent vertex v of u
\nif (dist[v] > dist[u] + weight(u, v))
\ndist[v] = dist[u] + weight(u, v)<\/p>\n[ad type=\u201dbanner\u201d]\n

Python Programming<\/strong><\/p>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Python%20program%20to%20find%20single%20source%20shortest%20paths%0A%23%20for%20Directed%20Acyclic%20Graphs%20Complexity%20%3AOV(V%2BE)%0Afrom%20collections%20import%20defaultdict%0A%20%0A%23%20Graph%20is%20represented%20using%20adjacency%20list.%20Every%0A%23%20node%20of%20adjacency%20list%20contains%20vertex%20number%20of%0A%23%20the%20vertex%20to%20which%20edge%20connects.%20It%20also%20contains%0A%23%20weight%20of%20the%20edge%0Aclass%20Graph%3A%0A%20%20%20%20def%20__init__(self%2Cvertices)%3A%0A%20%0A%20%20%20%20%20%20%20%20self.V%20%3D%20vertices%20%23%20No.%20of%20vertices%0A%20%0A%20%20%20%20%20%20%20%20%23%20dictionary%20containing%20adjacency%20List%0A%20%20%20%20%20%20%20%20self.graph%20%3D%20defaultdict(list)%0A%20%0A%20%20%20%20%23%20function%20to%20add%20an%20edge%20to%20graph%0A%20%20%20%20def%20addEdge(self%2Cu%2Cv%2Cw)%3A%0A%20%20%20%20%20%20%20%20self.graph%5Bu%5D.append((v%2Cw))%0A%20%0A%20%0A%20%20%20%20%23%20A%20recursive%20function%20used%20by%20shortestPath%0A%20%20%20%20def%20topologicalSortUtil(self%2Cv%2Cvisited%2Cstack)%3A%0A%20%0A%20%20%20%20%20%20%20%20%23%20Mark%20the%20current%20node%20as%20visited.%0A%20%20%20%20%20%20%20%20visited%5Bv%5D%20%3D%20True%0A%20%0A%20%20%20%20%20%20%20%20%23%20Recur%20for%20all%20the%20vertices%20adjacent%20to%20this%20vertex%0A%20%20%20%20%20%20%20%20if%20v%20in%20self.graph.keys()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20node%2Cweight%20in%20self.graph%5Bv%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20visited%5Bnode%5D%20%3D%3D%20False%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.topologicalSortUtil(node%2Cvisited%2Cstack)%0A%20%0A%20%20%20%20%20%20%20%20%23%20Push%20current%20vertex%20to%20stack%20which%20stores%20topological%20sort%0A%20%20%20%20%20%20%20%20stack.append(v)%0A%20%0A%20%0A%20%20%20%20\u201d\u2019%20The%20function%20to%20find%20shortest%20paths%20from%20given%20vertex.%0A%20%20%20%20%20%20%20%20It%20uses%20recursive%20topologicalSortUtil()%20to%20get%20topological%0A%20%20%20%20%20%20%20%20sorting%20of%20given%20graph.\u201d\u2019%0A%20%20%20%20def%20shortestPath(self%2C%20s)%3A%0A%20%0A%20%20%20%20%20%20%20%20%23%20Mark%20all%20the%20vertices%20as%20not%20visited%0A%20%20%20%20%20%20%20%20visited%20%3D%20%5BFalse%5D*self.V%0A%20%20%20%20%20%20%20%20stack%20%3D%5B%5D%0A%20%0A%20%20%20%20%20%20%20%20%23%20Call%20the%20recursive%20helper%20function%20to%20store%20Topological%0A%20%20%20%20%20%20%20%20%23%20Sort%20starting%20from%20source%20vertice%0A%20%20%20%20%20%20%20%20for%20i%20in%20range(self.V)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20visited%5Bi%5D%20%3D%3D%20False%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.topologicalSortUtil(s%2Cvisited%2Cstack)%0A%20%0A%20%20%20%20%20%20%20%20%23%20Initialize%20distances%20to%20all%20vertices%20as%20infinite%20and%0A%20%20%20%20%20%20%20%20%23%20distance%20to%20source%20as%200%0A%20%20%20%20%20%20%20%20dist%20%3D%20%5Bfloat(%22Inf%22)%5D%20*%20(self.V)%0A%20%20%20%20%20%20%20%20dist%5Bs%5D%20%3D%200%0A%20%0A%20%20%20%20%20%20%20%20%23%20Process%20vertices%20in%20topological%20order%0A%20%20%20%20%20%20%20%20while%20stack%3A%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Get%20the%20next%20vertex%20from%20topological%20order%0A%20%20%20%20%20%20%20%20%20%20%20%20i%20%3D%20stack.pop()%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Update%20distances%20of%20all%20adjacent%20vertices%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20node%2Cweight%20in%20self.graph%5Bi%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20dist%5Bnode%5D%20%3E%20dist%5Bi%5D%20%2B%20weight%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20dist%5Bnode%5D%20%3D%20dist%5Bi%5D%20%2B%20weight%0A%20%0A%20%20%20%20%20%20%20%20%23%20Print%20the%20calculated%20shortest%20distances%0A%20%20%20%20%20%20%20%20for%20i%20in%20range(self.V)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20print%20(%22%25d%22%20%25dist%5Bi%5D)%20if%20dist%5Bi%5D%20!%3D%20float(%22Inf%22)%20else%20%20%22Inf%22%20%2C%0A%20%0A%20%0Ag%20%3D%20Graph(6)%0Ag.addEdge(0%2C%201%2C%205)%0Ag.addEdge(0%2C%202%2C%203)%0Ag.addEdge(1%2C%203%2C%206)%0Ag.addEdge(1%2C%202%2C%202)%0Ag.addEdge(2%2C%204%2C%204)%0Ag.addEdge(2%2C%205%2C%202)%0Ag.addEdge(2%2C%203%2C%207)%0Ag.addEdge(3%2C%204%2C%20-1)%0Ag.addEdge(4%2C%205%2C%20-2)%0A%20%0A%23%20source%20%3D%201%0As%20%3D%201%0A%20%0Aprint%20(%22Following%20are%20shortest%20distances%20from%20source%20%25d%20%22%20%25%20s)%0Ag.shortestPath(s)\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

\u00a0<\/p>\n

Output:<\/p>\n

Following are shortest distances from source 1\r\nINF 0 2 6 5 3<\/pre>\n
Time Complexity:<\/strong> Time complexity of topological sorting is O(V+E). After finding topological order, the algorithm process all vertices and for every vertex, it runs a loop for all adjacent vertices. Total adjacent vertices in a graph is O(E). So the inner loop runs O(V+E) times. Therefore, overall time complexity of this algorithm is O(V+E).<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
shortest path directed acyclic graph
\nGiven a Weighted Directed Acyclic Graph and a source vertex in the graph, find the shortest path<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,4148],"tags":[83668,83672,83670,83664,83671,83667,83669,83665,83673,83666,79910,83675,83674],"class_list":["post-26687","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-python","tag-c-code-for-directed-acyclic-graph","tag-dag-shortest-path-algorithm","tag-dag-shortest-path-vs-dijkstra","tag-directed-acyclic-graph-algorithm","tag-directed-acyclic-graph-topological-sort","tag-directed-acyclic-graph-tutorial","tag-shortest-path-algorithm-in-data-structure","tag-shortest-path-dag-dynamic-programming","tag-shortest-path-dag-negative-weights","tag-shortest-path-directed-graph","tag-shortest-path-in-graph","tag-shortest-path-problem-example","tag-single-source-shortest-path-problem"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26687","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26687"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26687\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26687"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26687"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26687"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}