Shortest Path Algorithm

• Download source - 2.9 KB

Introduction

Shortest path algorithms are used in many real life applications, especially applications involving maps and artificial intelligence algorithms which are NP in nature. A graph is a collection of nodes \(V\) connected by edges \(E\) and can be expressed as \(G(V,E)\). Stands for vertices. These vertices and the connecting edges together can be imagined to form a three dimensional geometrical structure. In some cases, for each \((u,v)\) \(\epsilon E\) (here \(u,v,\) \(\epsilon V\) are vertices which are connected), there is a weight value assigned to it. This can also be called as "distance" or "cost" of connecting the two nodes. The shortest path algorithm traces the minimum distance (or cost) between two nodes \((u,v)\) which are either directly or indirectly connected. The weight values along each possible paths to the destination node from the source node are summed up, and the path with the minimum summation value is chosen as the shortest path.

We may represent a weighted graph \(G(V,E,w)\) as where the extra parameter represents the set of weight values across each edge. \(w:E \rightarrow \mathbb{R} - {0},w(e)\) Weight of the edge. Usually, shortest path algorithms are of time complexity \(\Omega (|V|)\) because every node needs to be visited at least once. In case of AI algorithms, the vertices are generated based on specific rules, and usually it’s a function of depth; because most nodes have more than one connection, we may also have non-polynomial relation between the depth and the number of nodes.

Algorithms like Dijkstra’s algorithm’s time complexity is \(O(|V|^{2})\) (note, \(|V|\) represent number of nodes and \(|E|\) represents number of edges). Note that the definition is actually a relation between the edge and a real number other than zero. This also shows that the weight values can be negative. So a modified version of the algorithm which also solves problems with negative weight edges is required. But doing this increases the time complexity; Dijkstra’s algorithm is a greedy algorithm, which selects the best possible path in the graph originating from a node, and later choosing the node with the least distance from the set of nodes yet to be visited, to further repeat the process with the newly selected node. Such an algorithm which solves graphs with negative weight values is Bellman Ford algorithm and its runtime complexity is \(O(|V|E|)\). Generally, \(|E| \geq 1\) unless there are disjoint nodes or graphs. Unless stated, the graphs discussed here are always assumed to not contain any disjoint sets or nodes.

Dijkstra’s Algorithm

This is a greedy algorithm which keeps selecting the node with the minimum weight from the list of nodes, to begin with.

Algorithm I

Dijkstra (G=(V,E,w),s,d),
// V stands for the  vertices
// E stands for edges.         
// w is the weight value for each
// s is the source node. 
// d is the destination node.

     // Q can be a min-priority queue to improve the                
     // runtime complexity of the algorithm which changes 
     // to.

               For each // is the minimum value in the set 
                       Let 
                     Be a node that can immediately reached by the   
                           Node 
                Then for each 
                    The distance from the source to the node   
                    Is modified as, 
                     If then    
                          
                            Else 
                         No change in distance value.
                            //is the parent node of 
       
                    If v = d then 
                                End search returning  and 
 
                // this ensures that the node is not
                // visited again
               End For loop // For each 
 End function Dijkstra (G (V, E, w), s, d)

In the above algorithm, pre and dis(s,u) refer to "previous link" and "distance from s to u" respectively. We can see that for each node that is at minimum among the other unvisited nodes, are selected first. So the time complexity is \(O(|V|^{2})\), because in the worst case scenario every node is visited, and again, if every node is connected to every other node, then both pairs of nodes are visited each time the algorithm iterates. So this ends up visiting \(|V|\) nodes for each node in the graph. But we don’t always consider the worst case, as its occurrence is rare, but we rather rely on the average case or the amortised analysis of the algorithm.

The above described algorithm shows the shortest path between two nodes, given that even negative weight values can be included.

Bellman Ford Algorithm

When there are negative weights in the graph, each path needs to be visited for times on the worse case. This shows that the time complexity is \(O(|V|E|)\). The reason that every edge is compulsorily visited is, if the algorithm misses a negative edge, the shortest path itself changes; and moreover the greedy approach fails because, once the final destination node is reached before visiting each edge, we cannot conclude that to be the shortest path. Let’s say that the Dijkstra’s algorithm returns the shortest path to the destination to be \(a_{source}\rightarrow b\rightarrow c\rightarrow e_{destination}\) in a graph with negative weight values. Let’s further consider that that path is of length \(x_{1}\).

And another path \(a_{source}\rightarrow b\rightarrow l\rightarrow m\) to be of length \(x_{2} > x_{1}\). Then there can be a negative edge, if when visited reduces the length to a value less than \(x_{1}\). From the algorithm, we can say that the node at the shortest distance to the destination is returned as the answer. But for the case involving negative weight values, a path that’s considered to be "longer" at that instant might not be as long as expected. Because, if it has a connecting path, that travels through a negative edge, its distance might reduce beyond the currently chosen shortest path. Let’s consider there exists a path \(m\rightarrow f\rightarrow e_{source}\) with a negative distance \(w\). So the new path \(a_{source}\rightarrow b\rightarrow l\rightarrow m\rightarrow f\rightarrow e_{destination}\) will be of length \(x_{2}+w\) which could also be \(x_{2}+w < x_{1}\). So we cannot conclude the shortest path until we have visited each path in the graph. Even if we have visited each path in the graph, the shortest path might be something else unless the process is carried over for \(N \leq |V|E|\) times. But not lesser than \(|V|\) times.

Algorithm II

BellmanFord(G(V, E, W),s,d), 
// V stands for the vertices.
// E stands for edges.
// w is the weight value for each.
// s is the source node. 
// d is the destination node.

    For i= 1 to  do 
                   // Q can be a min-priority queue to improve the
                   // runtime complexity of the algorithm which changes 
                   // to.
         
               For each // is the minimum value in the set 
                       Let 
                     Be a node that can immediately reached by the   
                           Node 
                Then for each 
                    The distance from the source to the node   
                    Is modified as, 
                     If then    
                          
                            Else 
                         No change in distance value.
                            //is the parent node of        
                    
                 // this ensures that the node is not
                 // visited again
               End For loop // For each 
        End For loop        // For i= 1 to  do
   Return Pre and Dis 
End function Dijkstra (G (V, E, w), s, d)

The above depicts the Bellman Ford algorithm. This algorithm, as we can see, always runs at the worst case of \(O(|V|E|)\). But we can modify it to run faster, by inserting an operation to check if there is any change after calling the ‘For each u∈Q_min’ loop, we can determine if we could terminate the process earlier. If there was no modification, then the function returns immediately.

Negative Cycles

There are many cases that are to be considered before the direct implementation of Bellman Ford algorithm. Because of involving negative edges, there are chances of having the shortest path of a graph’s loop undeterminable. For example, consider the case of having a graph with every edge having a negative weight value. Let’s consider that the Bellman Ford algorithm updates the distance of each node from the source node, by updating each edge for times. If every edge was negative, the shortest path that was obtained keeps becoming shorter each time we follow the same procedure (refer the Bellman Ford algorithm given in this article).

Definition

A negative edge cycle is defined as a cyclic path within that graph, which contains negative weight values and the net sum of each edge along the cyclic path sums up to a value less than zero. This causes the algorithm to never find the shortest path in the graph, and if such a scenario exists, then the solution becomes undefined.

This problem does not just arise when each edge in the graph has negative weight value, but also occurs when any arbitrary cyclic path in the graph has its edge values summing up to a value less than zero.

Reposting From

• http://www.creativitymaximized.com/2015/10/shortest-path-algorithm-elaborated.html

History

• 3^rd October, 2015: First written