BELLMAN FORD ALGORITHM IMPLEMENTATION IN C++
"Intelligence is the art of modifying our belief system until our hypothesis and theories start to correlate with the reality we observe."
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.
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.
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.
(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.
Subscribe to:
Posts (Atom)