{"id":659,"date":"2018-07-19T12:32:51","date_gmt":"2018-07-19T12:32:51","guid":{"rendered":"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/?post_type=chapter&#038;p=659"},"modified":"2018-12-21T10:50:06","modified_gmt":"2018-12-21T10:50:06","slug":"shortest-path-algorithm-ii","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/chapter\/shortest-path-algorithm-ii\/","title":{"rendered":"Shortest Path Algorithm II"},"content":{"raw":"<div><span style=\"float: right\"><a href=\"https:\/\/youtu.be\/gEqcnmlVShY\" target=\"_blank\" rel=\"noopener\"><img src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"epgp books\" width=\"75px\" height=\"75px;\" \/><\/a>\r\n<\/span><\/div>\r\n<div>\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Welcome to the e-PG Pathshala Lecture Series on Data Structures. In this module we will again discuss about shortest path algorithms.<\/p>\r\n&nbsp;\r\n\r\n<strong>Learning Objectives<\/strong>\r\n\r\n&nbsp;\r\n\r\nThe learning objectives of the module are as follows:\r\n\r\n&nbsp;\r\n\r\n\u2022\u00a0 To explain the Bellman-Ford algorithm\u00a0 for Single-source shortest paths\r\n\r\n\u2022\u00a0 To illustrate the Bellman-Ford Algorithm with an example\r\n\r\n\u2022\u00a0 To discuss the Floyd-Warshall Algorithm for All-Pairs Shortest Paths\r\n\r\n&nbsp;\r\n\r\n<strong>40.1 Recap<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Before we discuss other shortest path algorithms let us recall some basic procedures we used for Dijkstra\u2019s algorithm. For a graph G (V,E), the single-source shortest path algorithms with the start vertex s, keeps track of d[v] which indicates the shortest path weight from source to vertex v and p[v] which indicates the predecessor u of v in the shortest path. Algorithms keep track of d[v], p[v]. They are initialized as follows:<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-662 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-456.png\" alt=\"\" width=\"574\" height=\"327\" \/>\r\n\r\n&nbsp;\r\n\r\n<strong style=\"text-align: initial;font-size: 1em\">40.2 Single-source shortest paths<\/strong>\r\n\r\n<\/div>\r\n<div>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Two classic algorithms to solve single-source shortest path problem are Dijkstra\u2019s algorithm and Bellman-Ford algorithm. The Dijkstra\u2019s algorithm has been already discussed in the previous module and in this module we will discuss in detail the Bellman-Ford algorithm.<\/p>\r\n&nbsp;\r\n\r\n<strong>40.2.1 Dijkstra and Negative-Weight Edges<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Dijkstra algorithm is a greedy algorithm where it adds vertices by increasing distance but is faster than Bellman-Ford algorithm. However, it works only when the weights are all non-negative. If a node with a negative incident edge were to be added late to the cloud, it could mess up distances for vertices already in the cloud. For example in Figure 40.1 C\u2019s true distance is 1, but it is already in the cloud with d(C)=5.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-663 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-457.png\" alt=\"\" width=\"467\" height=\"260\" \/>\r\n\r\n&nbsp;\r\n\r\n<strong>40.3 Bellman-Ford Algorithm<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Bellman-Ford algorithm is a dynamic programming algorithm that solves the single source shortest path problem. The main advantage of the algorithm is that it works even when some weights are negative. Single-source shortest path problem computes \u03b4(s, v) and p[v] for all v \u00ce V. The algorithm allows negative edge weights - can detect negative cycles. The basic idea of this algorithm is as follows.<\/p>\r\n\r\n<ul>\r\n \t<li>Each edge is relaxed |V\u20131| times by making |V -1| passes over the whole edge set.<\/li>\r\n \t<li style=\"text-align: justify\">To make sure that each edge is relaxed exactly |V \u2013 1| times, it puts the edges in an unordered list and goes over the list |V \u2013 1| times.<\/li>\r\n<\/ul>\r\n<img class=\" wp-image-664 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-458.png\" alt=\"\" width=\"603\" height=\"243\" \/>\r\n\r\n&nbsp;\r\n\r\n<\/div>\r\n<strong><img class=\" wp-image-665 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-459.png\" alt=\"\" width=\"656\" height=\"602\" \/><\/strong>\r\n<div><\/div>\r\n<img class=\"size-full wp-image-666 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-460.png\" alt=\"\" width=\"618\" height=\"407\" \/>\r\n<div>\r\n\r\n<strong>40.5\u00a0 Bellman-Ford algorithm: Example 1<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong>The example has been adopted from <\/strong>\r\n\r\nwww.cs.bilkent.edu.tr\/~atat\/502\/SingleSourceSP.<strong>ppt<\/strong>\r\n\r\n&nbsp;\r\n\r\n<\/div>\r\n<div>\r\n\r\n<img class=\"size-full wp-image-667 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-461.png\" alt=\"\" width=\"677\" height=\"442\" \/>\r\n\r\n<img class=\"size-full wp-image-668 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-462.png\" alt=\"\" width=\"597\" height=\"286\" \/>\r\n\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-669 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-463.png\" alt=\"\" width=\"634\" height=\"613\" \/>\r\n\r\n&nbsp;\r\n\r\n<strong style=\"text-align: initial;font-size: 1em\">40.6 Bellman-Ford algorithm: Dynamic Programming<\/strong>\r\n\r\n<\/div>\r\n<div>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">For each node v, find the length of the shortest path to any node t that uses at most 1 edge, or write down \u221e if there is no such path. If v = t we get 0; if (v, t) \u2208 E then we get len(v, t); else just put down \u221e. Now, suppose for all v we have solved for length of the shortest path to t that uses i \u2212 1 or fewer edges.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">We can use the above to solve for the shortest path that uses i or fewer edges. The shortest path from v to t that uses i or fewer edges will first go to some neighbor x of v, and then take the shortest path from x to t that uses i\u22121 or fewer edges, which we\u2019ve already solved for. So, we just need to take the minimum over all neighbors x of v. At most i = n \u2212 1 edges need to be processed to obtain the answer. The main observation made here are as follows. (i) If there is a negative cycle, then there is no solution. Because adding this cycle again can always produces a less weighted path. (ii)\u00a0 If there is no negative cycle, a shortest path has at most |V|-1 edges. The basic idea behind solving this algorithm using dynamic programming is that for all the paths have at most 0 edge, find all the shortest paths, for all the paths have at most\u00a0<span style=\"font-size: 1em;text-align: initial\">1 edge, find all the shortest paths and so on and finally for all the paths have at most |V|-1 edge, find all the shortest paths. The algorithm for the above is given below:<\/span><\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\n&nbsp;\r\n\r\nBellman-Ford pseudocode:\r\n\r\ninitialize d[v][0] = infinity for v != t. d[t][i]=0 for all i.\r\n\r\nfor i=1 to n-1:\r\n\r\nfor each v != t:\r\n\r\nd[v][i] = min\r\n\r\n(v,x)2E\r\n\r\n(len(v,x) + d[x][i-1])\r\n\r\nFor each v, output d[v][n-1].\r\n\r\n&nbsp;\r\n\r\n<strong>40.6.1 Bellman-Ford algorithm: Example 2<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Based on the above idea, the shortest path from node 1 to other nodes of Figure 40.4 is discovered. The total number of nodes is 3 and hence the process repeats 3 times. First the shortest paths with 0-edge are discovered from vertex 1 to 1, 1 to 2 and 1 to 3. The path weights for 1 to 1, 1 to 2 and 1 to 3 are 0, \u221e and \u221e respectively (Figure 40.4).<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-670 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-464.png\" alt=\"\" width=\"644\" height=\"397\" \/>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Finally, the shortest paths with 2-edges are discovered from vertex 1 to 1, 1 to 2 and 1 to 3. The path weights for 1 to 1, 1 to 2 and 1 to 3 are 0, 10 and 11 respectively. The path from 1 to 3 changes from 20 to 10 since the 2-edge path is shorter than the 1-edge path (Figure 40.6).<\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\n<img class=\"size-full wp-image-671 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-465.png\" alt=\"\" width=\"517\" height=\"186\" \/>\r\n\r\n<strong>40.7 Bellman-Ford algorithm- Walkthrough<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Let us consider one more example for the graph given in Figure 40.7 (a). The same procedure mentioned above is repeated to find the shortest path from vertex 1.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-672 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-466.png\" alt=\"\" width=\"596\" height=\"604\" \/>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Now we find the shortest path from 1 with 1 edge which is 1-2 and 1-4. Hence the d value of 2 changes from \u00a5 to 6 and that of 4 changes from \u00a5 to 7 (Figure 40.7 (b)).<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-673 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-467.png\" alt=\"\" width=\"615\" height=\"590\" \/>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Now we find the shortest path from 1 with 2 edges which is 1-2-3 (d =11) and 1-4-3 (d=4). Hence the d value of 3 is 11\/4. The 2 edge path to 5 is 1-2-5 and so d value of 5 is \u00a5\/2 (Figure 40.7 (c)).<\/p>\r\n\r\n<\/div>\r\n<img class=\"size-full wp-image-674 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-468.png\" alt=\"\" width=\"458\" height=\"279\" \/>\r\n<div>\r\n\r\nThe shortest paths with negative cycle is shown in Figure 40.7 (f). The shortest path from 1 to 5 is 1-4-3-2-5 and its weight is -2.\r\n\r\n<\/div>\r\n<div>\r\n\r\n<img class=\"size-full wp-image-675 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-469.png\" alt=\"\" width=\"402\" height=\"257\" \/>\r\n\r\n&nbsp;\r\n\r\n<strong>40.8 All-Pair Shortest Path Algorithm<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">It aims at computing the shortest paths between all pairs of vertices in a directed graph G = (V, E). Each edge e (u, v) has a weight w which is a real number (i.e. Weight function w : E \u2192 R). The output is an n\u00d7 n matrix of shortest-path distances \u03b4(u, v). For example, let us consider graph in Figure 40.8. The all-pair shortest path algorithm finds the shortest path from vertex 1 to all the other vertices, vertex 2 to all other vertices and so on.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"size-full wp-image-676 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-470.png\" alt=\"\" width=\"264\" height=\"238\" \/>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The possible solutions for All-Pairs Shortest Paths is to run BELLMAN-FORD once from each vertex. The time complexity is O(V2E), which is O(V4) if the graph is dense (E = Q(V2)). If there are no negative-weight edges, we could run Dijkstra\u2019s algorithm once from each vertex. The time complexity is then O(VElogV) with binary heap and O(V3logV) if the graph is dense. Assume G=(V,E) is a graph such that c[v,w] \u00b3 0, where C is the matrix of edge costs. Find for each pair (v,w), the shortest path from v to w. In other words we need to find the matrix of shortest paths . Certainly this is a generalization of Dijkstra\u2019s. A dedicated All-Pairs Shortest Paths algorithm is called Floyd-Warshall Algorithm which is discussed in detail below.<\/p>\r\n&nbsp;\r\n\r\n<strong>40.9<\/strong>\u00a0<strong>Floyd-Warshall Algorithm<\/strong>\r\n\r\n&nbsp;\r\n\r\nFloyd-Warshall Algorithm uses nxn matrix A to compute the lengths of the shortest paths using a dynamic programming technique.\r\n\r\n<\/div>\r\n&nbsp;\r\n\r\nInitially, let Let A[i,j] = c[i,j] for all i,j &amp; i\u00b9j where c[i, j] is the cost matrix of the edges, i and j are vertices.\r\n\r\n&nbsp;\r\n\r\nIf (i,j) is not an edge, set A[i,j]=infinity and A[i,i]=0 .\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The main idea is to find Ak[i,j] = min (Ak-1[i,j] , Ak-1[i,k]+ Ak-1[k,j]) where Ak is the matrix after k-th iteration and path from i to j does not pass through a vertex higher than k.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">To find the shortest paths that uses 2 or fewer edges find A2, where multiplication is defined as <em>minimum of sums<\/em> instead sum of products. That is (A2)ij = min{ Aik + Akj | k =1..n} . This operation is O(n3). Using A2 you can find A4 and then A8 and so on. Therefore to find An we need log n operations. Hence the time complexity of this algorithm is O(log n* n3). The following is the pseudo code of Floyd-Warshall Implementation.<\/p>\r\n&nbsp;\r\n\r\nInitialize A[i,j] = C[i,j]\r\n\r\nInitialize all A[i,i] = 0\r\n\r\nfor k from 1 to n\r\n\r\nfor i from 1 to n\r\n\r\nfor j from 1 to n\r\n\r\nif (A[i,j] &gt; A[i,k]+A[k,j])\r\n\r\nA[i,j] = A[i,k]+A[k,j];\r\n\r\n&nbsp;\r\n\r\n<strong>Summary<\/strong>\r\n<ul>\r\n \t<li>Explained the Bellman-Ford algorithm for Single -source shortest paths<\/li>\r\n \t<li>Illustrated the Bellman-Ford Algorithm with an example<\/li>\r\n \t<li>Discussed the Floyd-Warshall Algorithm for All-Pairs Shortest Paths<\/li>\r\n<\/ul>\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td><strong>you can view video on Shortest Path Algorithm II<\/strong><\/td>\r\n<td><a href=\"https:\/\/youtu.be\/gEqcnmlVShY\" target=\"_blank\" rel=\"noopener\"><img class=\"alignnone wp-image-120\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"\" width=\"36\" height=\"36\" \/><\/a><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n<img class=\"size-full wp-image-677 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-471.png\" alt=\"\" width=\"676\" height=\"547\" \/>","rendered":"<div><span style=\"float: right\"><a href=\"https:\/\/youtu.be\/gEqcnmlVShY\" target=\"_blank\" rel=\"noopener\"><img decoding=\"async\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"epgp books\" width=\"75px\" height=\"75px;\" \/><\/a><br \/>\n<\/span><\/div>\n<div>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Welcome to the e-PG Pathshala Lecture Series on Data Structures. In this module we will again discuss about shortest path algorithms.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Learning Objectives<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>The learning objectives of the module are as follows:<\/p>\n<p>&nbsp;<\/p>\n<p>\u2022\u00a0 To explain the Bellman-Ford algorithm\u00a0 for Single-source shortest paths<\/p>\n<p>\u2022\u00a0 To illustrate the Bellman-Ford Algorithm with an example<\/p>\n<p>\u2022\u00a0 To discuss the Floyd-Warshall Algorithm for All-Pairs Shortest Paths<\/p>\n<p>&nbsp;<\/p>\n<p><strong>40.1 Recap<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Before we discuss other shortest path algorithms let us recall some basic procedures we used for Dijkstra\u2019s algorithm. For a graph G (V,E), the single-source shortest path algorithms with the start vertex s, keeps track of d[v] which indicates the shortest path weight from source to vertex v and p[v] which indicates the predecessor u of v in the shortest path. Algorithms keep track of d[v], p[v]. They are initialized as follows:<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-662 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-456.png\" alt=\"\" width=\"574\" height=\"327\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-456.png 574w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-456-300x171.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-456-65x37.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-456-225x128.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-456-350x199.png 350w\" sizes=\"auto, (max-width: 574px) 100vw, 574px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><strong style=\"text-align: initial;font-size: 1em\">40.2 Single-source shortest paths<\/strong><\/p>\n<\/div>\n<div>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Two classic algorithms to solve single-source shortest path problem are Dijkstra\u2019s algorithm and Bellman-Ford algorithm. The Dijkstra\u2019s algorithm has been already discussed in the previous module and in this module we will discuss in detail the Bellman-Ford algorithm.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>40.2.1 Dijkstra and Negative-Weight Edges<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Dijkstra algorithm is a greedy algorithm where it adds vertices by increasing distance but is faster than Bellman-Ford algorithm. However, it works only when the weights are all non-negative. If a node with a negative incident edge were to be added late to the cloud, it could mess up distances for vertices already in the cloud. For example in Figure 40.1 C\u2019s true distance is 1, but it is already in the cloud with d(C)=5.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-663 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-457.png\" alt=\"\" width=\"467\" height=\"260\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-457.png 467w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-457-300x167.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-457-65x36.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-457-225x125.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-457-350x195.png 350w\" sizes=\"auto, (max-width: 467px) 100vw, 467px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><strong>40.3 Bellman-Ford Algorithm<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Bellman-Ford algorithm is a dynamic programming algorithm that solves the single source shortest path problem. The main advantage of the algorithm is that it works even when some weights are negative. Single-source shortest path problem computes \u03b4(s, v) and p[v] for all v \u00ce V. The algorithm allows negative edge weights &#8211; can detect negative cycles. The basic idea of this algorithm is as follows.<\/p>\n<ul>\n<li>Each edge is relaxed |V\u20131| times by making |V -1| passes over the whole edge set.<\/li>\n<li style=\"text-align: justify\">To make sure that each edge is relaxed exactly |V \u2013 1| times, it puts the edges in an unordered list and goes over the list |V \u2013 1| times.<\/li>\n<\/ul>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-664 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-458.png\" alt=\"\" width=\"603\" height=\"243\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-458.png 491w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-458-300x121.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-458-65x26.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-458-225x91.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-458-350x141.png 350w\" sizes=\"auto, (max-width: 603px) 100vw, 603px\" \/><\/p>\n<p>&nbsp;<\/p>\n<\/div>\n<p><strong><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-665 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-459.png\" alt=\"\" width=\"656\" height=\"602\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-459.png 651w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-459-300x275.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-459-65x60.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-459-225x206.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-459-350x321.png 350w\" sizes=\"auto, (max-width: 656px) 100vw, 656px\" \/><\/strong><\/p>\n<div><\/div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-666 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-460.png\" alt=\"\" width=\"618\" height=\"407\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-460.png 618w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-460-300x198.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-460-65x43.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-460-225x148.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-460-350x231.png 350w\" sizes=\"auto, (max-width: 618px) 100vw, 618px\" \/><\/p>\n<div>\n<p><strong>40.5\u00a0 Bellman-Ford algorithm: Example 1<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>The example has been adopted from <\/strong><\/p>\n<p>www.cs.bilkent.edu.tr\/~atat\/502\/SingleSourceSP.<strong>ppt<\/strong><\/p>\n<p>&nbsp;<\/p>\n<\/div>\n<div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-667 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-461.png\" alt=\"\" width=\"677\" height=\"442\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-461.png 677w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-461-300x196.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-461-65x42.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-461-225x147.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-461-350x229.png 350w\" sizes=\"auto, (max-width: 677px) 100vw, 677px\" \/><\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-668 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-462.png\" alt=\"\" width=\"597\" height=\"286\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-462.png 597w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-462-300x144.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-462-65x31.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-462-225x108.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-462-350x168.png 350w\" sizes=\"auto, (max-width: 597px) 100vw, 597px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-669 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-463.png\" alt=\"\" width=\"634\" height=\"613\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-463.png 634w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-463-300x290.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-463-65x63.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-463-225x218.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-463-350x338.png 350w\" sizes=\"auto, (max-width: 634px) 100vw, 634px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><strong style=\"text-align: initial;font-size: 1em\">40.6 Bellman-Ford algorithm: Dynamic Programming<\/strong><\/p>\n<\/div>\n<div>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">For each node v, find the length of the shortest path to any node t that uses at most 1 edge, or write down \u221e if there is no such path. If v = t we get 0; if (v, t) \u2208 E then we get len(v, t); else just put down \u221e. Now, suppose for all v we have solved for length of the shortest path to t that uses i \u2212 1 or fewer edges.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">We can use the above to solve for the shortest path that uses i or fewer edges. The shortest path from v to t that uses i or fewer edges will first go to some neighbor x of v, and then take the shortest path from x to t that uses i\u22121 or fewer edges, which we\u2019ve already solved for. So, we just need to take the minimum over all neighbors x of v. At most i = n \u2212 1 edges need to be processed to obtain the answer. The main observation made here are as follows. (i) If there is a negative cycle, then there is no solution. Because adding this cycle again can always produces a less weighted path. (ii)\u00a0 If there is no negative cycle, a shortest path has at most |V|-1 edges. The basic idea behind solving this algorithm using dynamic programming is that for all the paths have at most 0 edge, find all the shortest paths, for all the paths have at most\u00a0<span style=\"font-size: 1em;text-align: initial\">1 edge, find all the shortest paths and so on and finally for all the paths have at most |V|-1 edge, find all the shortest paths. The algorithm for the above is given below:<\/span><\/p>\n<\/div>\n<div>\n<p>&nbsp;<\/p>\n<p>Bellman-Ford pseudocode:<\/p>\n<p>initialize d[v][0] = infinity for v != t. d[t][i]=0 for all i.<\/p>\n<p>for i=1 to n-1:<\/p>\n<p>for each v != t:<\/p>\n<p>d[v][i] = min<\/p>\n<p>(v,x)2E<\/p>\n<p>(len(v,x) + d[x][i-1])<\/p>\n<p>For each v, output d[v][n-1].<\/p>\n<p>&nbsp;<\/p>\n<p><strong>40.6.1 Bellman-Ford algorithm: Example 2<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Based on the above idea, the shortest path from node 1 to other nodes of Figure 40.4 is discovered. The total number of nodes is 3 and hence the process repeats 3 times. First the shortest paths with 0-edge are discovered from vertex 1 to 1, 1 to 2 and 1 to 3. The path weights for 1 to 1, 1 to 2 and 1 to 3 are 0, \u221e and \u221e respectively (Figure 40.4).<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-670 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-464.png\" alt=\"\" width=\"644\" height=\"397\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-464.png 644w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-464-300x185.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-464-65x40.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-464-225x139.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-464-350x216.png 350w\" sizes=\"auto, (max-width: 644px) 100vw, 644px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Finally, the shortest paths with 2-edges are discovered from vertex 1 to 1, 1 to 2 and 1 to 3. The path weights for 1 to 1, 1 to 2 and 1 to 3 are 0, 10 and 11 respectively. The path from 1 to 3 changes from 20 to 10 since the 2-edge path is shorter than the 1-edge path (Figure 40.6).<\/p>\n<\/div>\n<div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-671 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-465.png\" alt=\"\" width=\"517\" height=\"186\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-465.png 517w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-465-300x108.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-465-65x23.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-465-225x81.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-465-350x126.png 350w\" sizes=\"auto, (max-width: 517px) 100vw, 517px\" \/><\/p>\n<p><strong>40.7 Bellman-Ford algorithm- Walkthrough<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Let us consider one more example for the graph given in Figure 40.7 (a). The same procedure mentioned above is repeated to find the shortest path from vertex 1.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-672 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-466.png\" alt=\"\" width=\"596\" height=\"604\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-466.png 596w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-466-296x300.png 296w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-466-65x66.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-466-225x228.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-466-350x355.png 350w\" sizes=\"auto, (max-width: 596px) 100vw, 596px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Now we find the shortest path from 1 with 1 edge which is 1-2 and 1-4. Hence the d value of 2 changes from \u00a5 to 6 and that of 4 changes from \u00a5 to 7 (Figure 40.7 (b)).<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-673 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-467.png\" alt=\"\" width=\"615\" height=\"590\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-467.png 615w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-467-300x288.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-467-65x62.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-467-225x216.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-467-350x336.png 350w\" sizes=\"auto, (max-width: 615px) 100vw, 615px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Now we find the shortest path from 1 with 2 edges which is 1-2-3 (d =11) and 1-4-3 (d=4). Hence the d value of 3 is 11\/4. The 2 edge path to 5 is 1-2-5 and so d value of 5 is \u00a5\/2 (Figure 40.7 (c)).<\/p>\n<\/div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-674 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-468.png\" alt=\"\" width=\"458\" height=\"279\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-468.png 458w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-468-300x183.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-468-65x40.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-468-225x137.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-468-350x213.png 350w\" sizes=\"auto, (max-width: 458px) 100vw, 458px\" \/><\/p>\n<div>\n<p>The shortest paths with negative cycle is shown in Figure 40.7 (f). The shortest path from 1 to 5 is 1-4-3-2-5 and its weight is -2.<\/p>\n<\/div>\n<div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-675 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-469.png\" alt=\"\" width=\"402\" height=\"257\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-469.png 402w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-469-300x192.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-469-65x42.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-469-225x144.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-469-350x224.png 350w\" sizes=\"auto, (max-width: 402px) 100vw, 402px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><strong>40.8 All-Pair Shortest Path Algorithm<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">It aims at computing the shortest paths between all pairs of vertices in a directed graph G = (V, E). Each edge e (u, v) has a weight w which is a real number (i.e. Weight function w : E \u2192 R). The output is an n\u00d7 n matrix of shortest-path distances \u03b4(u, v). For example, let us consider graph in Figure 40.8. The all-pair shortest path algorithm finds the shortest path from vertex 1 to all the other vertices, vertex 2 to all other vertices and so on.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-676 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-470.png\" alt=\"\" width=\"264\" height=\"238\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-470.png 264w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-470-65x59.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-470-225x203.png 225w\" sizes=\"auto, (max-width: 264px) 100vw, 264px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The possible solutions for All-Pairs Shortest Paths is to run BELLMAN-FORD once from each vertex. The time complexity is O(V2E), which is O(V4) if the graph is dense (E = Q(V2)). If there are no negative-weight edges, we could run Dijkstra\u2019s algorithm once from each vertex. The time complexity is then O(VElogV) with binary heap and O(V3logV) if the graph is dense. Assume G=(V,E) is a graph such that c[v,w] \u00b3 0, where C is the matrix of edge costs. Find for each pair (v,w), the shortest path from v to w. In other words we need to find the matrix of shortest paths . Certainly this is a generalization of Dijkstra\u2019s. A dedicated All-Pairs Shortest Paths algorithm is called Floyd-Warshall Algorithm which is discussed in detail below.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>40.9<\/strong>\u00a0<strong>Floyd-Warshall Algorithm<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Floyd-Warshall Algorithm uses nxn matrix A to compute the lengths of the shortest paths using a dynamic programming technique.<\/p>\n<\/div>\n<p>&nbsp;<\/p>\n<p>Initially, let Let A[i,j] = c[i,j] for all i,j &amp; i\u00b9j where c[i, j] is the cost matrix of the edges, i and j are vertices.<\/p>\n<p>&nbsp;<\/p>\n<p>If (i,j) is not an edge, set A[i,j]=infinity and A[i,i]=0 .<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The main idea is to find Ak[i,j] = min (Ak-1[i,j] , Ak-1[i,k]+ Ak-1[k,j]) where Ak is the matrix after k-th iteration and path from i to j does not pass through a vertex higher than k.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">To find the shortest paths that uses 2 or fewer edges find A2, where multiplication is defined as <em>minimum of sums<\/em> instead sum of products. That is (A2)ij = min{ Aik + Akj | k =1..n} . This operation is O(n3). Using A2 you can find A4 and then A8 and so on. Therefore to find An we need log n operations. Hence the time complexity of this algorithm is O(log n* n3). The following is the pseudo code of Floyd-Warshall Implementation.<\/p>\n<p>&nbsp;<\/p>\n<p>Initialize A[i,j] = C[i,j]<\/p>\n<p>Initialize all A[i,i] = 0<\/p>\n<p>for k from 1 to n<\/p>\n<p>for i from 1 to n<\/p>\n<p>for j from 1 to n<\/p>\n<p>if (A[i,j] &gt; A[i,k]+A[k,j])<\/p>\n<p>A[i,j] = A[i,k]+A[k,j];<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Summary<\/strong><\/p>\n<ul>\n<li>Explained the Bellman-Ford algorithm for Single -source shortest paths<\/li>\n<li>Illustrated the Bellman-Ford Algorithm with an example<\/li>\n<li>Discussed the Floyd-Warshall Algorithm for All-Pairs Shortest Paths<\/li>\n<\/ul>\n<table>\n<tbody>\n<tr>\n<td><strong>you can view video on Shortest Path Algorithm II<\/strong><\/td>\n<td><a href=\"https:\/\/youtu.be\/gEqcnmlVShY\" target=\"_blank\" rel=\"noopener\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-120\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"\" width=\"36\" height=\"36\" \/><\/a><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-677 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-471.png\" alt=\"\" width=\"676\" height=\"547\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-471.png 676w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-471-300x243.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-471-65x53.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-471-225x182.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-471-350x283.png 350w\" sizes=\"auto, (max-width: 676px) 100vw, 676px\" \/><\/p>\n","protected":false},"author":3,"menu_order":40,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["dr-t-v-geetha"],"pb_section_license":""},"chapter-type":[],"contributor":[59],"license":[],"class_list":["post-659","chapter","type-chapter","status-publish","hentry","contributor-dr-t-v-geetha"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters\/659","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/users\/3"}],"version-history":[{"count":8,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters\/659\/revisions"}],"predecessor-version":[{"id":998,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters\/659\/revisions\/998"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters\/659\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/media?parent=659"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapter-type?post=659"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/contributor?post=659"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/license?post=659"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}