Path Queries

We will run Dijkstra Algorithm for all vertices in this approach and store the minimum distance in an array. Then we can answer the queries using this distance array.
 

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 push 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 matrix graph, graph from the given edges.
• We will initialize an array dis of size (V+1)*(V+1) to store all pairs of the shortest distance.
• Now we will run this Dijkstra function V times. We will iterate for each vertex index from 1 to V.
  • Set dist as dijkstra(graph, V, index) and store the minimum distances of source index to all vertices from dist into dis[index].
  • The value dis[index1][index2] will represent the minimum distance between vertex index1 and index2.
• We will now answer queries by iterating through all queries.
  • For each query node1,node2 we will append dis[node1][node2] into ans array.
• We will return ans array.

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

Floyd Warshall Algorithm is a dynamic programming approach in which we try to find the shortest distance of a pair of vertices using an intermediate vertex as shown 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.
  • 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:
      • 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.
• We will now answer queries by iterating through all queries.
  • For each query node1,node2 append dist[node1]node2] into the ans array.
• We will return the ans array.