Search This Blog

Simplicity is the ultimate sophistication.” — Leonardo da Vinci
Contact me:

Saturday 3 October 2015

Bellman Ford Algorithm implementation in c++


Shortest path algorithm: Elaborated

Shortest path algorithm
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.

Featured post

Why increasing complexity is not good?

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