Given a weighted graph and a source vertex in the graph, find the shortest paths from the source to all the other vertices in the given graph....

Bellman Ford’s algorithm Like other Dynamic Programming Problems, the algorithm calculates shortest paths in a bottom-up manner. It first calculates the shortest distances which have at-most one edge in the path. Then, it calculates the shortest paths with at-most 2 edges, and so on. After the i-th iteration of outer loop, the shortest paths with at most i edges are calculated. There can be maximum |V| – 1 edge in any simple path, that is why the outer loop runs |v| – 1 time. The idea is, assuming that there is no negative weight cycle if we have calculated shortest paths with at most i edges, then an iteration over all edges guarantees to give the shortest path with at-most (i+1) edges...

Finding the shortest way is becoming more important in a world where time and distance matter. There are multiple shorted path algorithms exists. Therefore, in this article, we will compare the shortest path algorithms on the basis of their complexity and their performance, which will help us to use the correct algorithm according to our requirements....

Given a directed graph and a source vertex in the graph, the task is to find the shortest distance and path from source to target vertex in the given graph where edges are weighted (non-negative) and directed from parent vertex to source vertices....

Given an undirected weighted graph of N nodes and M edges in the form of a tuple lets say {X, Y, Z} such that there is an edge with cost Z between X and Y. We are supposed to compute the minimum cost of traversal from node 1 to N. However, we can perform one operation before the traversal such that we can reduce the cost of any edge lets say, C to C / 2 (integer division)....

Given a directed weighted graph and the source and destination vertex. The task is to find the sum of shortest distance on the path going from source to destination and then from destination to source such that both the paths have at least a common vertex other than the source and the destination. Note: On going from destination to source, all the directions of the edges are reversed.Examples:...

Given an undirected unweighted graph. The task is to find the length of the shortest cycle in the given graph. If no cycle exists print -1....

Given a weighted directed graph with N nodes and M edges along with a source node S, use Parallel Programming to find the shortest distance from the source node S to all other nodes in the graph. The graph is given as an edge list edges[][] where for each index i, there is an edge from edges[i][0] to edges[i][1] with weight edges[i][2]....

In this article, we will be discussing one of the most commonly known shortest-path algorithms i.e. Dijkstra’s Shortest Path Algorithm which was developed by Dutch computer scientist Edsger W. Dijkstra in 1956. Moreover, we will do a complexity analysis for this algorithm and also see how it differs from other shortest-path algorithms....

Given a graph and a source vertex in the graph, find the shortest paths from the source to all vertices in the given graph.We have discussed Dijkstra’s Shortest Path algorithm in the below posts....

Given a graph of N Nodes and E edges in form of {U, V, W} such that there exists an edge between U and V with weight W. You are given an integer K and source src and destination dst. The task is to find the cheapest cost path from given source to destination from K stops.Examples:...

We recommend reading the following two posts as a prerequisite for this post....