Shortest Path Problem in Graph in Data Structure

Shortest Path Problem:

The shortest path problem is about finding a path between 

$2$

 vertices in a graph such that the total sum of the edges weights is minimum.

This problem could be solved easily using (BFS) if all edge weights were (

$1$

), but here weights can take any value. Three different algorithms are discussed below depending on the use-case.

Bellman Ford's Algorithm:

Bellman Ford's algorithm is used to find the shortest paths from the source vertex to all other vertices in a weighted graph. It depends on the following concept: Shortest path contains at most 

$n-1$

 edges, because the shortest path couldn't have a cycle.So why shortest path shouldn't have a cycle ?

There is no need to pass a vertex again, because the shortest path to all other vertices could be found without the need for a second visit for any vertices.

Algorithm Steps:

• The outer loop traverses from 
  $0$
   : 
  $n-1$
  .
• Loop over all edges, check if the next node distance > current node distance + edge weight, in this case update the next node distance to "current node distance + edge weight".

This algorithm depends on the relaxation principle where the shortest distance for all vertices is gradually replaced by more accurate values until eventually reaching the optimum solution. In the beginning all vertices have a distance of "Infinity", but only the distance of the source vertex = 

$0$

, then update all the connected vertices with the new distances (source vertex distance + edge weights), then apply the same concept for the new vertices with new distances and so on.

Dijkstra's Algorithm

Dijkstra's algorithm has many variants but the most common one is to find the shortest paths from the source vertex to all other vertices in the graph.

Algorithm Steps:

• Set all vertices distances = infinity except for the source vertex, set the source distance = 
  $0$
  .
• Push the source vertex in a min-priority queue in the form (distance , vertex), as the comparison in the min-priority queue will be according to vertices distances.
• Pop the vertex with the minimum distance from the priority queue (at first the popped vertex = source).
• Update the distances of the connected vertices to the popped vertex in case of "current vertex distance + edge weight < next vertex distance", then push the vertex
  with the new distance to the priority queue.
• If the popped vertex is visited before, just continue without using it.
• Apply the same algorithm again until the priority queue is empty.

For demonstration we will consider the below graph:

Step Wise Execution

Step 1:

Mark Vertex 1 as the source vertex. Assign a cost zero to Vertex 1 and (infinite to all other vertices). The state is as follows:

Step 2:

For each of the unvisited neighbours (Vertex 2, Vertex 3 and Vertex 4) calculate the minimum cost as Min(current cost of vertex under consideration, sum of cost of vertex 1 and connecting edge). Mark Vertex 1 as visited , in the diagram we border it black. The new state would be as follows:

Step 3:

Choose the unvisited vertex with minimum cost (vertex 4) and consider all its unvisited neighbours (Vertex 5 and Vertex 6) and calculate the minimum cost for both of them. The state is as follows:

Step 4:

Choose the unvisited vertex with minimum cost (vertex 2 or vertex 5, here we choose vertex 2) and consider all its unvisited neighbours(Vertex 3 and Vertex 5) and calculate the minimum cost for both of them. Now, the current cost of Vertex 3 is [4] and the sum of (cost of Vertex 2 + cost of edge (2,3) ) is 3 + 4 = [7]. Minimum of 4, 7 is 4. Hence the cost of vertex 3 won’t change. By the same argument the cost of vertex 5 will not change. We just mark the vertex 2 as visited, all the costs remain same. The state is as follows:

Step 5:

Choose the unvisited vertex with minimum cost (vertex 5) and consider all its unvisited neighbours(Vertex 3 and Vertex 6) and calculate the minimum cost for both of them. Now, the current cost of Vertex 3 is [4] and the sum of (cost of Vertex 5 + cost of edge (5,3) ) is 3 + 6 = [9]. Minimum of 4, 9 is 4. Hence the cost of vertex 3 won’t change. Now, the current cost of Vertex 6 is [6] and the sum of (cost of Vertex 5 + cost of edge (3,6) ) is 3 + 2 = [5]. Minimum of 6, 5 is 45. Hence the cost of vertex 6 changes to 5. The state is as follows:

Step 6:

Choose the unvisited vertex with minimum cost (vertex 3) and consider all its unvisited neighbours(none). So mark it visited. The state is as follows:

Step 7:

Choose the unvisited vertex with minimum cost (vertex 6) and consider all its unvisited neighbours (none). So mark it visited. The state is as follows:

Now there is no unvisited vertex left and the execution ends. At the end we know the shortest paths for all the vertices from the source vertex 1. Even if we know the shortest path length, we do not know the exact list of vertices which contributes to the shortest path until we maintain them separately or the data structure supports it.

Floyd–Warshall's Algorithm

Floyd–Warshall's Algorithm is used to find the shortest paths between between all pairs of vertices in a graph, where each edge in the graph has a weight which is positive or negative. The biggest advantage of using this algorithm is that all the shortest distances between any $2$ vertices could be calculated in $O\left(V^3\right)$, where $V$ is the number of vertices in a graph.

The Algorithm Steps:

For a graph with $N$ vertices:

• Initialize the shortest paths between any $2$ vertices with Infinity.
• Find all pair shortest paths that use $0$ intermediate vertices, then find the shortest paths that use $1$intermediate vertex and so on.. until using all $N$ vertices as intermediate nodes.
• Minimize the shortest paths between any $2$ pairs in the previous operation.
• For any $2$ vertices $(i,j)$ , one should actually minimize the distances between this pair using the first $K$nodes, so the shortest path will be: $min\left(dist\right[i\left]\right[k]+dist[k\left]\right[j],dist[i\left]\right[j\left]\right)$.

$dist\left[i\right]\left[k\right]$ represents the shortest path that only uses the first $K$ vertices, $dist\left[k\right]\left[j\right]$ represents the shortest path between the pair $k,j$. As the shortest path will be a concatenation of the shortest path from $i$ to $k$, then from $k$ to $j$.