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