{"id":632,"date":"2018-07-19T11:56:23","date_gmt":"2018-07-19T11:56:23","guid":{"rendered":"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=632"},"modified":"2018-12-21T10:48:39","modified_gmt":"2018-12-21T10:48:39","slug":"shortest-path-algorithm-i","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/chapter\/shortest-path-algorithm-i\/","title":{"rendered":"Shortest Path Algorithm – I"},"content":{"raw":"
\"epgp<\/a>\r\n<\/span><\/div>\r\n
\r\n\r\n \r\n\r\n \r\n\r\n \r\n

Welcome to the e-PG Pathshala Lecture Series on Data Structures. In this module we will discuss about Shortest Path Algorithm.<\/p>\r\n \r\n\r\nLearning Objectives<\/strong>\r\n\r\n \r\n\r\nThe learning objectives of the module are as follows:\r\n\r\n \r\n\r\n\u2022 To understand the Shortest Path problem and its variants\r\n\r\n\u2022 To discuss the properties of Shortest path\r\n\r\n\u2022 To explain the Dijkstra\u2019s Algorithm\r\n\r\n\u2022 To illustrate the Dijkstra\u2019s Algorithm with an example\r\n\r\n \r\n\r\n39.1 Recap<\/strong>\r\n\r\n \r\n

Topological sort is a method of arranging the vertices in a directed acyclic graph (DAG), as a sequence, such that no vertex appear in the sequence before its predecessor. The properties of the Topological sort and the step -by-step description had been discussed with an example.<\/p>\r\n \r\n\r\n39.2 Shortest Path Problem<\/strong>\r\n\r\n \r\n

In this module we discuss the shortest path algorithm. S hortest Path Problem is usually associated with a weighted graph that has two vertices u<\/em> and v<\/em>, and we want to find a path of minimum total weight between u<\/em> and v.<\/em> Length of a path is the sum of the weights of its edges.<\/p>\r\n \r\n

Example: Shortest path between Bangalore and Madurai. An example of a graph for shortest path is given in Figure 39.1. Applications of shortest path problem include Internet packet routing, Flight reservations and Driving directions.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n<\/div>\r\n

\r\n

The shortest path algorithm is associated with a directed weighted graph and the path length is sum of weights of the edges on the path. The source vertex is the place where the path begins and the destination vertex is the vertex where the path ends. Once the source and destination are finalized the vertices in the increasing order is reported from the source vertex. We construct the shortest path edge by edge; at each step adding one new edge, corresponding to construction of shortest path to the current new vertex.<\/p>\r\n \r\n\r\n39.2.1 Shortest Path Notations<\/strong>\r\n\r\n \r\n

For each vertex v \u00ce V where V is the set of vertices. \u03b4(s, v) is shortest-path weight and d[v] is the shortest-path weight estimate. Initially, d[v]=\u00a5 and d[v]\u00e0\u03b4(s,v) as algorithm progresses. p[v] = predecessor<\/strong> of v on a shortest path from s and if no predecessor exists, p[v] = NIL. p induces a tree called the shortest-path tree as shown in Figure<\/strong> 39.2.<\/strong><\/p>\r\n\"\"\r\n\r\n \r\n\r\n39.3 Shortest Path Algorithm<\/strong>\r\n\r\n \r\n

The input to the algorithm is the Directed graph G = (V, E), with V being the set of vertices and E being the edges. A weight function w : E \u2192 R is associated with each edge of the graph. A path is denoted by a sequence of vertices. The weight of path p = \u00e1v0, v1, . . . , vk\u00f1, is the weight of the edges between the vertices in the path. The Shortest-path weight from u to v: d(u, v) = min w(p) : if there exists a path p or p from u to v \u00a5 :otherwise. Note that there might be multiple shortest paths from u to v. There may be many types of shortest path algorithms.<\/p>\r\n \r\n\r\n39.3.1 Initialization<\/strong>\r\n\r\n \r\n

All the shortest-paths algorithms start with INITIALIZE-SINGLE-SOURCE. Initially for every vertex v in G, d[v] the shortest path estimate is set to \u00a5 and the p[v], the predecessor of every vertex v is set to Nil. d[s], the shortest path estimate of source node is set to 0.<\/p>\r\n \r\n\r\n<\/div>\r\n\"\"\r\n

\r\n\r\n\u00a0 \u00a0d[s] \u2190 0\r\n\r\n \r\n\r\n39.2.2<\/strong>\u00a0 Shortest Path Tree<\/strong>\r\n\r\n \r\n

For every node v<\/em> \u00ce<\/em> V, \u03c0[v]<\/em> is the predecessor of v<\/em> in shortest path from source s<\/em> to v.<\/em> This value is set to Nil if does not exist. All our algorithms will output a shortest-path tree whose root is the source s and the edges are (\u03c0[v],v).<\/em> The shortest path between s<\/em> and v<\/em> is the unique tree path from root s to v<\/em>. Consider Source node 1 and destination node 7, a direct path between the nodes will cost 14, however a shorter path through two other nodes costs only 11 (Figure 39.3).<\/p>\r\n \r\n\r\n\"\"\r\n\r\n39.3 Shortest Path Variants<\/strong>\r\n\r\n \r\n\r\nThere are many variants of the shortest path algorithms. They are:\r\n\r\n \r\n\r\nSingle-source single-destination (1-1): <\/strong>Find the shortest path from source s<\/em> to destination v<\/em>.\r\n\r\n \r\n\r\nSingle-source all-destination(1-Many): <\/strong>Find the shortest path from s<\/em> to each vertex v<\/em>.\r\n\r\n \r\n

Single-destination shortest-paths (Many-1): <\/strong>Find a shortest path to a given destination <\/em>vertex t <\/em>from each vertex v<\/em>.<\/p>\r\n \r\n

All-pairs shortest-paths problem (Many-Many): <\/strong>Find a shortest path from u<\/em> to v<\/em> for every pair of vertices u<\/em> and v<\/em>.<\/p>\r\n \r\n\r\nSingle source\/All destinations <\/strong>-nonnegative edge cost\r\n\r\n \r\n\r\nNeed to solve: <\/strong>determine a shortest path from v<\/em> to each of the remaining vertices of G<\/em>.\r\n\r\n \r\n\r\n39.3.1 Single-destination shortest paths<\/strong>\r\n\r\n \r\n

Among the shortest path algorithms given above the single destination shortest paths is about finding a shortest path to a given destination vertex t<\/strong> from each vertex v. Here we reverse the direction of each edge and finding the distances between every pair of vertices in a weighted directed graph G. Figure 39.4 shows the example of the Single source\/All destinations <\/strong>-nonnegative edge cost where we need to determine a shortest path from v<\/em> to each of the remaining vertices of G<\/em>.<\/p>\r\n\r\n<\/div>\r\n\"\"\r\n

\r\n\r\n \r\n\r\n39.3.2 Shortest Path Properties<\/strong>\r\n\r\n \r\n

If some path from s to v contains a negative cost cycle, there does not exist a shortest path. Otherwise, there exists a shortest s-v that is simple. A negative cycle can produce arbitrarily long negative paths by traversing cycle a number of times. The negative-weight edges may form negative-weight cycle. If such cycles are reachable from the source, then \u03b4(s, v) the shortest-path weight is not properly defined .<\/p>\r\n \r\n\r\n39.4 Relaxation Process<\/strong>\r\n\r\n \r\n

For each vertex v, we maintain an upper bound d[v] on the weight of shortest path from s to v and d[v] initialized to infinity. Relaxing<\/strong> an edge (u, v) = testing whether we can improve the shortest path to v found so far by going through u. d[v] is the weight of the path to vertex v, d[u] is the weight of the path to verte x u, w[u,v] is weight of edge [u,v] and p[v] indicates the predecessor of v in the shortest path to it (Figure 39.5).<\/p>\r\n

If d[v] > d[u] + w(u, v) and we can improve the shortest path to v . The updated d[v] => d[v]=d[u]+w(u,v) and p[v] is updated as => p[v] \u2190 u<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\nRelaxing an edge (<\/span>u<\/em>, <\/span>v<\/em>) consists of testing whether we can improve the shortest path to <\/span>v<\/em> found so far by going through <\/span>u<\/em>, then updating <\/span>d<\/em>[<\/span>v<\/em>] and p[<\/span>v<\/em>] accordingly. A relaxation step <\/span>may <\/strong>either<\/span> decrease <\/strong>the value of the shortest-path estimate <\/span>d<\/em>[<\/span>v<\/em>] and update <\/span>v<\/em>\u2019s predecessor p[<\/span>v<\/em>], or cause <\/span>no change<\/strong>.<\/span>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n39.5 Shortest Path Properties<\/strong>\r\n\r\n \r\n\r\nNow let us define some properties of shortest paths.\r\n\r\n \r\n\r\n39.5.1 Triangle Inequality<\/strong>\r\n\r\n \r\n

For any edge (u, v), we have (s; v) (s; u)+w(u; v). The weight of the shortest path from s to v is no greater than the weight of the shortest path from s to u plus the weight of the edge from u to v. For all (u, v) \u00ce E, we have:<\/p>\r\n \r\n\r\n\u03b4 (s, v) \u2264 \u03b4 (s, u) + w (u, v)\r\n\r\n \r\n\r\nIf u is on the shortest path to v we have the equality sign (Figure 39.6).\r\n\r\n \r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n39.5.2 Optimal substructure property<\/strong>\r\n\r\n \r\n

All sub-paths of shortest paths are also shortest paths. The shortest path problem has the following optimal substructure property. If a node x lies in the shortest path from a source node u to destination node v then the shortest path from u to v is combination of shortest path from u to x and shortest path from x to v.<\/p>\r\n \r\n\r\n39.5.3 Upper-bound property<\/strong>\r\n\r\n \r\n\r\nWe always have d[v] \u2265 \u03b4 (s, v) for all v. The estimate never rises since the relaxation process is so defined that it only lowers the estimate (Figure 39.7).\r\n\r\n \r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n\u00a0<\/strong>39.5.4 Convergence property<\/strong>\r\n\r\n<\/div>\r\n

\r\n\r\nIf s\u00a0 then u \u2192 v is a shortest path, and if d[u] = \u03b4(s, u) at any time prior to relaxing edge (u, v), d[v] = \u03b4(s, v) at all times after relaxing (u, v).\r\n\r\n<\/div>\r\n
\r\n\r\nAS shown in Figure 39.8, If d[v] > \u03b4(s, v) \u00de<\/em> after relaxation:\r\n\r\n<\/div>\r\n
\r\n\r\nd[v] = d[u] + w(u, v) and\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 d[v] = 5 + 2 = 7.\r\n\r\n \r\n

Otherwise, the value remains unchanged, because it must have already been the shortest path value.<\/p>\r\n \r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n39.5.5 Path relaxation property<\/strong>\r\n\r\n \r\n

Let p = \u00e1v0, v1, . . . , vk\u00f1 be a shortest path from s = v0 to vk. If we relax, in order, (v0, v1), (v1, v2), . . . , (vk-1, vk), even intermixed with other relaxations, then d[vk ] = \u03b4 (s, vk).<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n 39.5.6 Predecessor-subgraph property<\/strong>\r\n\r\n \r\n\r\n\"\"\r\n\r\n<\/div>\r\n \r\n\r\n39.6 Applications<\/strong>\r\n

\r\n

Some of the general types of applications of shortest path algorithms include minimization of the total distance<\/em> traveled, minimization of the total cost<\/em> of a sequence of activities, minimization of the total time<\/em> of a sequence of activities. Application areas include network optimization, packet routing, image segmentation, computer-assisted surgery, computer games, DNA analysis, injection molding, operator scheduling , production planning, re-allocation of resources, approximation of piecewise linear functions and VLSI physical design. As discussed the shortest path algorithms find applications in many diverse areas.<\/p>\r\n \r\n\r\n39.7\u00a0 Relaxation Summary<\/strong>\r\n\r\n \r\n

All algorithms in this module call INITIALIZE-SINGLE-SOURCE and then repeatedly relax edges. Relaxation is the only means by which shortest-path estimates and predecessors change. The shortest path algorithms differ in how many times<\/strong> they relax each edge and the order in which they relax edges<\/strong>. Bellman-Ford algorithm relaxes each edge many times, while Dijkstra\u2019s algorithm for directed acyclic graphs relax each edge exactly once.<\/p>\r\n \r\n\r\n39.8\u00a0 Algorithms<\/strong>\r\n\r\n \r\n

Dijkstra\u2019s algorithm and Bellman-Ford algorithm both use the common operations of Initialization and Relaxation. In Dijkstra\u2019s algorithm negative weights are not allowed. In the Bellman-Ford algorithm negative weights are allowed but negative cycles reachable from the source are not allowed.<\/p>\r\n \r\n\r\n39.9\u00a0 Dijkstra\u2019s Algorithm<\/strong>\r\n\r\n \r\n

The steps and assumptions of the Dijkstra\u2019s algorithm are as follows:<\/p>\r\n \r\n

    \r\n \t
  1. The distance of a vertex v<\/em><\/strong> from a vertex s<\/em><\/strong> is the length of a shortest path between s<\/em><\/strong> and v.<\/em><\/strong><\/li>\r\n \t
  2. Dijkstra\u2019s algorithm computes the distances of all the vertices from a given start vertex s.<\/em><\/strong><\/li>\r\n \t
  3. Assumptions are made that<\/li>\r\n<\/ol>\r\n