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.

// runtime complexity
of the algorithm which changes
// to
.


For each
//
is the minimum value in the set 



Let

Node 

Then for each 

The distance from the source to the
node

Is modified as,
If
then


Else
No change
in distance value.



If v = d then
End search
returning
and 



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


// runtime complexity
of the algorithm which changes
// to
.


For each
//
is the minimum value in the set 



Let

Node 

Then for each 

The distance
from the source to the node

Is modified as,
If
then


Else
No change
in distance value.




// 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
and
and
to 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