Introduction
 In graph theory, the shortest path problem is the problem of finding a path between two vertices/nodes (as source and destination) in a graph such that the sum of the weights/costs of its constituent edges route is minimized.
 The shortest path problem is considered as –
 The singlepair shortest path problem: It includes –
 The singlesource shortest path problem, in which we have to find the shortest paths from a source vertex (v) to all other vertices in the graph.
 The singledestination shortest path problem, in which we have to find the shortest paths from all vertices in the directed graph to a single destination vertex v. This can be reduced to the singlesource shortest path problem by reversing the arcs in the directed graph.
 The allpairs shortest path problem, in which we have to find the shortest paths between every pair of vertices (v, v’) in the graph.
 The singlepair shortest path problem: It includes –
Definition
 The shortest path problem is the problem of finding a path between two vertices/nodes between the source & destination node in a graph such that the sum of the weights of its constituent edges is minimized.
Characteristics
 The shortest path problem is applied with a Directed, Undirected or Mixed graph.
 Here, the shortest path in a graph from one vertex to another is the least number of edges or least total weight, etc.
Use/Application
 To find directions between physical locations i.e. in web mapping such as in MapQuest or Google Maps.
 In the transport sector for Vehicles routing problems.
 To optimize the various problems.
 In Telecommunication sectors.
 To sort out the logistics problems.
 Critical path analysis in project management.
Algorithms of Shortest Path Problem
 There are two famous algorithms to find out the shortest path problems. These are –
Dijkstra’s Algorithm (Single Source Shortest Path[SSSP] Problem)
Introduction
 This algorithm was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.
 The SingleSource Shortest Path (SSSP) problem consists of finding the shortest paths between a given vertex (v) and all other vertices in the graph.
Definition
 Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a nonnegative weighted, directed, or nondirected graph.
Characteristics
 Dijkstra’s algorithm solves the singlesource shortest path problem with nonnegative/positive edge weight or costs only.
 It is a type of greedy algorithm.
 Dijkstra’s algorithm works on the principle of BFS with a priority queue.
BellmanFord Algorithm (Single Source Shortest Path[SSSP] Problem)
Definition
 The BellmanFord algorithm is a popular algorithm used to find the shortest path in a weighted directed graph from a single source vertex to all other vertices. It can handle graphs even with negative weight edges but detects negative cycles.
Characteristics
 BellmanFord algorithm solves the singlesource shortest path problem with both nonnegative/positive or negative edge weight or cost.
 BellmanFord algorithm can handle graphs with both directed and undirected edges.
 The algorithm works by iteratively relaxing the edges of the graph. Relaxing an edge means updating the distance to the destination vertex if a shorter path is found. The algorithm repeatedly relaxes all edges in the graph until no further improvements can be made.
 The time complexity of the BellmanFord algorithm is O(V * E), where V is the number of vertices and E is the number of edges in the graph.
 BellmanFord algorithm can handle graphs with negative edge weights and can also detect negativeweight cycles.
 BellmanFord algorithm is less efficient than some other algorithms, such as Dijkstra’s algorithm, for graphs without negative edge weights.
 Steps of the BellmanFord algorithm:

Initialize the graph:
 Set the distance of the source vertex to 0.
 Set the distance of all other vertices to infinity.
 Also, create an array to store the predecessor of each vertex.

Iterate over all edges V – 1 time, where V is the number of vertices in the graph.
 For each edge (u, v) with weight w, if the distance to v can be improved by taking the path through u (distance[u] + w < distance[v]), update the distance[v] to the new shorter distance.

Check for negativeweight cycles:
 Iterate over all edges again and if any distance can still be improved, it means the graph contains a negativeweight cycle. This condition is used to detect and report the presence of negative cycles in the graph.

If no negative cycles are detected, the algorithm terminates, and the distances and predecessors represent the shortest paths from the source vertex to all other vertices.

At the end of the algorithm, the distance array will contain the shortest distances from the source vertex to all other vertices in the graph. If there are no negativeweight cycles, these distances will be the shortest paths.

FloydWarshall Algorithm (All Pair Shortest Path/APSP Problem)
 The FloydWarshall algorithm is an efficient algorithm used to find the shortest path between all pairs of vertices in a weighted directed graph, including graphs with negative edge weights.
 The FloydWarshall algorithm supports the AllPairs Shortest Path (APSP) problem consists of finding the shortest path between all pairs of vertices in the graph.
 It works based on the concept of dynamic programming.
 It works for both nonnegative/positive or negative edge weight or cost.
 The time complexity of the FloydWarshall algorithm is O(V^{3}), where V is the number of vertices in the graph. The space complexity is O(V^{2}) to store the distance and “next” matrices.
 The Steps of the FloydWarshall algorithm are:

Initialize a matrix, called the distance matrix, with the initial distances between vertices. If there is an edge between vertices u and v, set the corresponding entry in the matrix as the weight of that edge. If there is no edge, set the entry to infinity. Additionally, set the diagonal entries of the matrix to 0.

Perform a triple nested loop that iterates over all vertices in the graph. In each iteration, consider each pair of vertices (u, v) and check if the path from u to v can be improved by going through a third vertex, let’s call it k. The distance matrix entry for the pair (u, v) is updated as the minimum of the current distance and the sum of the distance from u to k and the distance from k to v.

After the triple nested loop completes, the distance matrix will contain the shortest path distances between all pairs of vertices in the graph.

0 Comments