Shortest Path

In this approach, we will calculate the shortest path between all pairs using the values of already computed values. This algorithm is known as Floyd Warshall Algorithm.

Floyd Warshall Algorithm is a dynamic programming approach in which the shortest distance of a pair is tried to minimize using an intermediate vertex whose value is already calculated as given below:

dist[index1][index2]=min(dis[index1][index2],dis[index1][k] + dis[k][index2])  

Where k is the intermediate vertex.

Algorithm:

• Floyd Warshall Algorithm:
  • Make an array dist of size (V+1)*(V+1) to store the shortest distance between all pairs of vertices.
  • Initialize all values of the array by maximum integer value because, in the beginning, we assume that all vertices are unreachable.
  • For all vertices index from 1 to V.
    • set dist[index][index] as 0 (distance between same vertices is 0).
  • Set the values of the edge weights into dist from the given edges(edge weight will be 1.).
  • Using each vertex from 1 to V as intermediate vertex k, do the following steps:
    • For a pair between index1 and index2, we are trying to minimize its minimum distance using intermediate vertex k. We will iterate k from 1 to V.
      • Set dist[index1][index2]  as the minimum of dist[index1][index2] and dist[index1][k] + dist[k][index2].
• Values of the Shortest distance between each pair are calculated.
• Return the value of dist[src][dest] (Shortest distance between src and dest).

We will run Dijkstra Algorithm for vertex ‘src’ and store the minimum distance of all vertices from vertex ‘src’ in an array in this approach. Then we can return the shortest distance between ‘src’ and ‘dest’. 

Dijkstra Algorithm is one of the most popular algorithms in graph theory. A single-source shortest path algorithm gives the shortest path length to all vertices from a given vertex known as the source vertex. It is a greedy algorithm that uses a priority queue(Binary Heap) to pick the shortest distance edges until the minimum distance of all vertices is calculated.

Algorithm:

• Dijkstra Algorithm:
  • We will define a function dijkstra(graph,n, source) where graph is the given graph,n is the number of vertices in the graph, and source is the source vertex.
  • Create an array dist with size n+1  to store the minimum distance of all vertices from source.
  •  Initialize all its values with maximum integer value because at the beginning. We assume that all vertices are unreachable.
  • Set dist[source] as 0.
  • We will now create a min-priority queue in which we will insert elements in the form of [distance, vertex] and extract the minimum distance path in each step.
  • We will also create an array visited to track vertices whose minimum distance is already calculated.
  • Initialize visited array with 0 as no vertex is visited yet.
  • Insert [dist[source],source] into the priority queue.
  • While all vertices are not visited, do the following steps:
    • Delete the minimum distance vertex cur from the queue and mark it as visited.
    • Now traverse by all the vertices connected to cur and if the vertex index is not visited yet and check if dist[index] is greater than dist[cur]+graph[cur][index], then set dis[index] as dis[cur] + graph[cur][index] and push [dis[index],index] into the priority queue.
  • The minimum distance of all vertices from the source is calculated, return the dist array.
• Make an adjacency list of the graph named graph from the given edges(edge weight will be the one.)
• Call the function dijikstra(graph, V, src) for the source as src and store its values in an array dis.
• Return dis[dest].(The shortest distance between src and dest.)

This approach will use breadth-first search traversal to find the shortest path between src and dest. Breadth-First Search is the most common graph traversal technique which satisfies some property. BFS can be related similar to level order traversal in trees.

We will maintain a queue and run BFS starting from vertex src till vertex dest is found and keep track of the traversal order. After visiting any specific node, we will insert all its children in the queue that have never been visited before.

Algorithm:

• Initialize the variable ans, which stores the shortest distance between src and dest.
• Prepare an adjacency list named graph from the given edges of the graph. (Edge weight is one).
• We will make a queue que to keep track of the order of traversal.
• To keep track of visited vertices, we will initialize an array visited of size V with all values to zero as all vertices are unvisited initially.
• The queue will be inserted in a tuple containing vertex and distance of the vertex from the vertex src.
• Insert [src,0] into the queue and set visited[cur] as 1.
• While que is not empty, do the following steps:
  • Set cur to the currently popped vertex.
  • Set dis to the distance of the currently popped vertex.
  • If cur is equal to dest, our search is completed simply by storing ans as dist. The dis corresponds to the shortest distance from src to dest, and we will break the while loop.
  • Traverse all vertices idx connected to graph[cur]:
    • Check if idx is not visited yet, insert [idx,dis+1] into the que. (dis + 1 because path length is increased by one).
    • We will make the vertex idx visited by setting visited[idx] as 1.
• Return the variable ans.