Shortest Path PDF

Preview

Summary

Shortest Path...

Description

Shortest Path Problem In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between two intersections on a road map may be modeled as a special case of the shortest path problem in graphs, where the vertices correspond to intersections and the edges correspond to road segments, each weighted by the length of the segment.

We have 4 different approaches for shortest path problems: 1. 2. 3. 4.

Single source single destination problem (SSSD) Single source multiple destination problem (SSMD) Multiple source single destination problem (MSSD) Multiple source multiple destination problem (MSMD)

The most important algorithms for solving this problem are: 1) Dijkstra’s Algorithm: solves the single-source shortest path problem with non-negative edge weight. 2) Bellman-Ford Algorithm: solves the single-source problem if edge weights may be negative.

Dijkstra’s Algorithm Dijkstra is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. For a given source node in the graph, the algorithm finds the shortest path between that node and every other. It can also be used for finding the shortest paths from a single node to a single destination node by stopping the algorithm once the shortest path to the destination node has been determined. For example, if the nodes of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road (for simplicity, ignore red lights, stop signs, toll roads and other obstructions), Dijkstra's algorithm can be used to find the shortest route between one city and all other cities. The Dijkstra algorithm uses labels that are positive integers or real numbers, which are totally ordered. It can be generalized to use any labels that are partially ordered, provided the subsequent labels (a subsequent label is produced when traversing an edge) are monotonically non-decreasing. This generalization is called the Generic Dijkstra shortest-path algorithm.Dijkstra's algorithm uses a data structure for storing and querying partial solutions sorted by distance from the start.

Algorithm Let the node at which we are starting be called the initial node. Let the distance of node Y be the distance from the initial node to Y. Dijkstra's algorithm will assign some initial distance values and will try to improve them step by step. 1. Mark all nodes unvisited. Create a set of all the unvisited nodes called the unvisited set. 2. Assign to every node a distance value: set it to zero for our initial node and to infinity for all other nodes. Set the initial node as current. 3. For the current node, consider all of its unvisited neighbors and calculate their distances through the current node. Compare the newly calculated distance to the current assigned value and assign the smaller one. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B through A will be 6 + 2 = 8. If B was previously marked with a distance greater than 8 then change it to 8. Otherwise, the current value will be kept. 4. When we are done considering all of the unvisited neighbors of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again. 5. If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest distance among the nodes in the unvisited set is infinity (when planning a complete traversal; occurs when there is no connection between the initial node and remaining unvisited nodes), then stop. The algorithm has finished. 6. Otherwise, select the unvisited node that is marked with the smallest distance, set it as the new "current node", and go back to step 3. When planning a route, it is actually not necessary to wait until the destination node is "visited" as above: the algorithm can stop once the destination node has the smallest distance among all "unvisited" nodes (and thus could be selected as the next "current").

Dijkstra's Algorithm only works for graphs with non-negative weights. 1 function Dijkstra (Graph, source): 2 3 create vertex set Q 4 5 for each vertex v in Graph: 6 dist[v] ← INFINITY 7 prev[v] ← UNDEFINED 8 add v to Q 10 dist[source] ← 0 11 12 while Q is not empty: 13 u ← vertex in Q with min dist[u] 14 15 remove u from Q 16 17 for each neighbor v of u: // only v that are still in Q 18 new_dist ← dist[u] + length (u, v)

19 20 21 22 23

if new_dist < dist[v]: dist[v] ← new_dist prev[v] ← u return dist[], prev[]

If we are only interested in a shortest path between vertices source and target, we can terminate the search after line 15 if u = target.

Bellman- Ford Algorithm The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers. Negative edge weights are found in various applications of graphs, hence the usefulness of this algorithm. If a graph contains a "negative cycle" (i.e. a cycle whose edges sum to a negative value) that is reachable from the source, then there is no cheapest path: any path that has a point on the negative cycle can be made cheaper by one more walk around the negative cycle. In such a case, the Bellman–Ford algorithm can detect and report the negative cycle. Like Dijkstra's algorithm, Bellman–Ford proceeds by relaxation, in which approximations to the correct distance are replaced by better ones until they eventually reach the solution. In both algorithms, the approximate distance to each vertex is always an overestimate of the true distance, and is replaced by the minimum of its old value and the length of a newly found path. However, Dijkstra's algorithm uses a priority queue to greedily select the closest vertex that has not yet been processed, and performs this relaxation process on all of its outgoing edges; by contrast, the Bellman–Ford algorithm simply relaxes all the edges. In each of these repetitions, the number of vertices with correctly calculated distances grows, from which it follows that eventually all vertices will have their correct distances. This method allows the Bellman–Ford algorithm to be applied to a wider class of inputs than Dijkstra.

In this example graph, assuming that A is the source and edges are processed in the worst order, from right to left, it requires the full |V|−1 or 4 iterations for the distance estimates to converge. Conversely, if the edges are processed in the best order, from left to right, the algorithm converges in a single iteration. function BellmanFord(list vertices, list edges, vertex source) distance[],predecessor[] // // // //

This implementation takes in a graph, represented as lists of vertices and edges, and fills two arrays (distance and predecessor) about the shortest path from the source to each vertex

// Step 1: initialize graph for each vertex v in vertices: distance[v] = inf //Initialize the distance of vertices to infinity predecessor[v] = null // And having a null predecessor distance [source] = 0

// The distance from the source to itself is zero

// Step 2: relax edges repeatedly for i from 1 to size(vertices)-1: for each edge (u, v) with weight w in edges: if distance[u] + w < distance[v]: distance[v] = distance[u] + w predecessor[v] = u // Step 3: check for for each edge (u, v) if distance[u] + error "Graph

negative-weight cycles with weight w in edges: w < distance[v]: contains a negative-weight cycle"

return distance[], predecessor[]

Simply put, the algorithm initializes the distance to the source to 0 and all other nodes to infinity. Then for all edges, if the distance to the destination can be shortened by taking the edge, the distance is updated to the new lower value. At each iteration i that the edges are scanned, the algorithm finds all shortest paths of at most length i edges (and possibly some paths longer than i edges). Since the longest possible path without a cycle can be |V|-1 edges, the edges must be scanned |V|-1 times to ensure the shortest path has been found for all nodes. A final scan of all the edges is performed and if any distance is updated, then a path of length |V| edges has been found which can only occur if at least one negative cycle exists in the graph.

Example Let us understand the algorithm with following example graph. Let the given source vertex be 0. Initialize all distances as infinite, except the distance to source itself. Total number of vertices in the graph is 5, so all edges must be processed 4 times.

Let all edges are processed in following order: (B, E), (D, B), (B, D), (A, B), (A, C), (D, C), (B, C), (E, D). We get following distances when all edges are processed first time. The first row in shows initial distances. The second row shows distances when edges (B, E), (D, B), (B, D) and (A, B) are processed. The third row shows distances when (A, C) is processed. The fourth row shows when (D, C), (B, C) and (E, D) are processed.

The first iteration guarantees to give all shortest paths which are at most 1 edge long. We get following distances when all edges are processed second time (The last row shows final values).

The second iteration guarantees to give all shortest paths which are at most 2 edges long. The algorithm processes all edges 2 more times. The distances are minimized after the second iteration, so third and fourth iterations don’t update the distances....