Maximizing your creativity, the Intelligent Dream: Shortest path algorithm: Elaborated

Shortest path algorithm

Program for Bellman Algorithm

By K Sreram

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,

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

” 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

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

// 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,

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

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 each

’ 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).

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

. 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

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