Search This Blog

Simplicity is the ultimate sophistication.” — Leonardo da Vinci
Contact me: sreramk360@gmail.com

Saturday, 3 October 2015

Shortest path algorithm: Elaborated


Shortest path algorithm
Email: sreramk@outlook.com
Shortest path algorithms are used in may real life applications, especially applications involving maps and artificial intelligence algorithms which are NP in nature. A graph is a collection of nodes connected by edges  and can be expressed as. 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 (here  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  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 as where the extra parameter represents the set of weight values across each edge. Weight of the edge. Usually, shortest path algorithms are of time complexity 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 connections, we may also have non-polynomial relation between the depth and the number of nodes.
Algorithms like Dijkstra’s algorithm’s time complexity is (note, represents number of nodes and represents number of edges). Dijkstra’s algorithm holds only for the situations where. But from the definition of a weighted graph given above, weight values can also be negative. So a modified version of the algorithm which also solves problems with negative weight edge is required. But this modified algorithm would require a greater runtime-time complexity; Dijkstra’s algorithm is a greedy algorithm, which selects the best possible path to every node in the graph, originating from source. But Dijkstra’s algorithm fails to solve problems that have negative weight values. In scenarios where negative weight values are present, another algorithm called Bellman Ford algorithm is used. But its runtime complexity is. Which is far greater than Dijkstra’s algorithm. Generally,  unless there are disjoint nodes or graphs. Unless stated, the graphs discussed here are always assumed to not contain any disjoint sets or nodes.


A brief outline on Dijkstra’s algorithm
There are several variations of this algorithm. The most prominent ones are the algorithms that run at time complexity and. The only difference is, the one that runs with the time complexity uses a priority queue.
The algorithm given below is the one that runs at .
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,  and  refers to “previous link” and “distance from  to” respectively. With min-queue implementation, the node which is at minimum distance from the source is selected first. So following this algorithm, we know that in the worst case, operations are done. We can write. So the time complexity is in the worst case scenario. It is more prominent to write as. And are related by an inequality, so there is a long range of values can take. Hence it is better to consider it as a separate parameter.    
Let’s consider the worst case when every node in the graph is connected to every other node. So now this algorithm ends up visiting  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. But the worst case (and sometimes the average case) is required for our clear understanding of the algorithm (Only amortised and average case analysis is used in real life applications).   

A brief outline on 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. 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  in a graph with negative weight values. Let’s further consider that that path is of length.
And another path  to be of length. Then there can be a negative edge, if when visited reduces the length to a value less than. 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 to exist a path  with a negative distance. So the new path  will be of length  which could also be. 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 times. But not lesser than 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. But we can modify it to run faster, by inserting an operation to check if there is any change after calling the ‘For eachloop, 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).  
Simplified 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 exist, 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.  
It is definitely required to compare both the algorithms for better understanding. The time complexity of Dijkstra’s algorithm is of many variations, because as there is room for determining how we choose the elements from the list. And depending on the kind for problem, we can have variations that runs much faster. In the above case, while discussing about Dijkstra’s algorithm, we considered  to be the path with the minimum distance from the source.

Example for a negative cycle:
 
The above is an example graph with two negative cycles. From the definition, the cyclic path that has its weight value summing up to zero is the negative cycle. The negative cycles are,, . Note that summing up the weight values across  also sums up to a value less than zero, but connects and connects  so this becomes impossible to reach from or . Hence it is not counted as a cycle. Observe the case where there is a loop between just two nodes; even these cases are to be considered. So it is obvious that so is also a “negative cycle”. And  is also a negative cycle. Because this graph has two negative cycles, it is meaningless to use Bellman Ford algorithm to find the shortest path as the shortest path does not exist.
Let’s see why these negative cycles make the graph’s shortest path undefined. Consider the simplest loop. For the sake of maintaining the simplicity, let’s consider the subgraph  for our analysis. During the first iteration process, let’s consider that the distance form source to to be set as andandto be set as. During the first iteration process,  distance from is set as. Now, the distance to get set as. Next, the path is tested, and yet again we see a modification. This time the distance to is set as. Now, is considered to be at a distance from the source.
Now as we follow the same procedure again starting from, is left unmodified because. But still, this doesn’t stop the algorithm from visiting and as it’s a rule that every node must be visited in Bellman Ford algorithm.  But the distance of form is updated as. Now we have the distance to set as. This time,  distance get remodified as. Now we have to be at a distance from the source. If we keep repeating these steps over and over again, the value keeps decreasing and after infinite iterations it becomes. Hence the shortest path is undefined. But cases where there aren’t any negative edges, the distance values of each node remains same after interations. Where.   


I have also submitted a copy of this article to codeprojects.com here.
 

No comments:

Post a Comment

Featured post

Why complicating matters is not good

“ Simplicity is the ultimate sophistication.” — Leonardo da Vinci Why is complicating things wrong ? - K Sr...