Path Queries
You are given a weighted, undirected graph with ‘V’ vertices numbered from 1 to ‘V’ and ‘E’ bidirectional edges.

You have to answer ‘Q’ queries. Every query has two integers, ‘u’, ‘v’, representing the vertices. Your task is to print the shortest distance between ‘u’ and ‘v’ and print -1 if there is no path.

For example:

For the given graph, we have to find the shortest distance between vertices 1 and 3. The shortest distance between 1 and 3 is 2 (via 1 2 3). Hence, the answer is 2.

Input Format:

The first line of the input contains an integer, 'T,’ denoting the number of test cases. The first line of each test case contains three integers ‘V’, ‘E’, ‘Q’, denoting the number of vertices, the number of edges in the graph, and the number of queries. The Next ‘E’ lines of each test case have three integers ‘u’,’v’,’w’ corresponding to vertices ‘u’ and ‘v’ are connected with a weight ‘w’. The Next ‘Q’ lines of each test case have two integers, ‘u’,’v’ representing two vertices.

Output Format:

For each test case, print ‘Q’ lines, each line has one integer corresponding to the minimum distance for the given query. Print the output of each test case in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1

Question

Path Queries

You are given a weighted, undirected graph with ‘V’ vertices numbered from 1 to ‘V’ and ‘E’ bidirectional edges.

You have to answer ‘Q’ queries. Every query has two integers, ‘u’, ‘v’, representing the vertices. Your task is to print the shortest distance between ‘u’ and ‘v’ and print -1 if there is no path.

For example:

altImage

For the given graph, we have to find the shortest distance between vertices 1 and 3. 
The shortest distance between 1 and 3 is 2 (via 1 <-> 2<-> 3). Hence, the answer is 2.

Input Format:

The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains three integers ‘V’, ‘E’, ‘Q’, denoting the number of vertices, the number of edges in the graph, and the number of queries.

The Next ‘E’ lines of each test case have three integers ‘u’,’v’,’w’ corresponding to vertices ‘u’ and ‘v’ are connected with a weight ‘w’.

The Next ‘Q’ lines of each test case have two integers, ‘u’,’v’ representing two vertices.

Output Format:

For each test case, print ‘Q’ lines, each line has one integer corresponding to the minimum distance for the given query.

Print the output of each test case in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= V <= 100
1 <= E <= (V *(V - 1)) / 2
1 <= Q <= 10^5 
1 <= u , v <= V
1 <= w <= 10^6

Time limit: 1 sec

Accepted Answer

Dijkstra Algorithm

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.

Space Complexity: OtherExplanation:

O(V^2), where V is the number of vertices in the graph.

The O(V^2) space is used to store the minimum distance between all pairs of vertices, and in total, there are V*V=V^2 pairs. The adjacency matrix also requires the O(V^2) space. Hence, the overall space complexity is O(V^2).

Time Complexity: OtherExplanation:

O(V*(V+E)*log(V) + Q), where V and E are the numbers of vertices and edges in the graph, and Q is the number of queries.

The time complexity of insert, delete operation on priority queue is O(log(V)).

The time complexity of the Dijkstra Algorithm:

V times delete operation while extracting the minimum value vertex :O(V *log(V))

E times insert operation while traversing neighbor vertices: O(E*log(V))

So,the total time complexity of Dijkstra Algorithm is O((V+E)*log(V)).

We are running Dijkstra Algorithm V times and answering Q queries, and each query takes O(1) time. Hence the overall time complexity will be O(V*(V+E)*log(V) +Q).

Java (SE 1.8)


/*
	Time Complexity: O(V*(V+E)*log(V) + Q)
	Space Complexity: O(V^2)
	
	Where V and E are the number of vertices and edges in the graph and Q is the number of queries
*/
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class The_Comparator implements Comparator> {
	public int compare(ArrayList str1, ArrayList str2) {
		int first_Str;
		int second_Str;
		first_Str = str1.get(0);
		second_Str = str2.get(0);
		if (first_Str == second_Str) {
			if (str1.get(1) > str2.get(0)) {
				return 1;
			}
		}
		if (first_Str > second_Str) {
			return 1;
		} else {
			return -1;
		}
	}
}

public class Solution {
	static int INT_MAX = 1000000000;

	private static int[] dijkstra(int[][] graph, int n, int source) {

		// Dist array
		int dist[] = new int[n + 1];
		Arrays.fill(dist, INT_MAX);
		dist[source] = 0;

		// Maintain a Priority Queue
		PriorityQueue> pq = new PriorityQueue(new The_Comparator());
		int visited[] = new int[n + 1];

		pq.add(new ArrayList<>(Arrays.asList(dist[source], source)));

		while (!pq.isEmpty()) {
			ArrayList l = pq.poll();

			// The variable cur is the current popped vertex
			int cur = l.get(1);

			// Marking cur vertex as visited
			visited[cur] = 1;

			for (int index = 1; index < n + 1; ++index) {

				// Checking if there is a edge between index and cur and index is not visited
				// yet
				if (visited[index] == 0 && graph[cur][index] != -1) {

					// Checking the distance can be minimized or not
					if (dist[index] > (dist[cur] + graph[cur][index])) {
						dist[index] = dist[cur] + graph[cur][index];

						// Inserting tuple of dist[index] and index in priority queue
						pq.add(new ArrayList<>(Arrays.asList(dist[index], index)));
					}
				}
			}
		}

		// Returning the dist array
		return dist;

	}

	public static int[] pathQueries(int v, int e, int q, int[][] edges, int[][] queries) {

		// Building dist array to store the shortest distance of each pair
		int[][] graph = new int[v + 1][];

		// The graph[i][j] will be -1 if i and j are not connect by an edge
		for (int i = 0; i < v + 1; i++) {
			int distances[] = new int[v + 1];
			Arrays.fill(distances, -1);
			graph[i] = distances;
		}

		// Setting the values of weights from the edges.
		for (int i = 0; i < edges.length; i++) {
			int[] edge = edges[i];

			// Given graph is an undirected graph,so edge will be bidirectional
			graph[edge[0]][edge[1]] = edge[2];
			graph[edge[1]][edge[0]] = edge[2];
		}

		// The dis array to store the shortest distance of all pairs
		int[][] dis = new int[v + 1][];

		// Setting dist[index][index] as 0 as the distance between same vertices is 0.
		for (int index = 1; index < v + 1; ++index) {
			graph[index] = dijkstra(graph, v, index);
		}

		// The ans array to store the answers of queries.
		int ans[] = new int[q];

		for (int i = 0; i < queries.length; ++i) {
			int[] query = queries[i];

			int node1 = query[0];
			int node2 = query[1];

			// Answer for the query
			int distance = graph[node1][node2];

			// If distance is equal to INT_MAX, then the vertices are unreachable
			if (distance == INT_MAX) {
				ans[i] = -1;
			} else {
				ans[i] = distance;
			}
		}
		return ans;
	}

}

Python (3.5)

"""

    Time Complexity: O(V*(V+E)*log(V) + Q)

    Space Complexity: O(V^2)



    Where V and E are the number of vertices and edges in the graph and Q is the number of queries

"""



import heapq

from sys import maxsize

INT_MAX = maxsize



def dijkstra(graph, n, source):

    

    # Dist array 

    dist = [INT_MAX for i in range(n + 1)]

    

    dist[source] = 0

    

    # Maintain a Priority Queue

    pq = []

    

    visited = [0 for i in range(n + 1)]

    pq.append([dist[source], source])

    

    heapq.heapify(pq)

    

    while (len(pq) > 0):

        

        l = heapq.heappop(pq)

        

        # The variable cur is the current popped vertex

        cur = l[1]

        

        # Marking cur vertex as visited

        visited[cur] = 1

        

        for index in range(1, n + 1):

            

            # Checking if there is a edge between index and cur and index is not visited yet

            if (visited[index] == 0 and graph[cur][index] != -1 ):

                

                # Checking the distance can be minimized or not

                if (dist[index] > (dist[cur] + graph[cur][index])):

                    

                    dist[index] = dist[cur] + graph[cur][index]

                    

                    # Inserting tuple of dist[index] and index in priority queue

                    heapq.heappush(pq, [dist[index], index])



    # Returning the dist array

    return dist





def pathQueries(v, e, q, edges, queries):



    # Buliding adjacency matrix for the given graph

    # The graph[i][j] will be -1 if i and j are not connect by an edge

    graph = [[-1 for j in range(v + 1)] for i in range(v + 1)]



    for edge in edges:

        

        # Given graph is an undirected graph,so edge will be bidirectional

        graph[edge[0]][edge[1]] = edge[2]

        graph[edge[1]][edge[0]] = edge[2]



    # The dis array to store the shortest distance of all pairs

    dis = [0 for i in range(v + 1)]



    for index in range(1, v + 1):

        

        dist = dijkstra(graph, v, index)

        dis[index] = dist



    # The ans array to store the answers of the queries

    ans = []

    

    for query in queries:

        

        node1 = query[0]

        node2 = query[1]

        

        # Answer for the query

        distance = dis[node1][node2]



        # If distance is equal to INT_MAX, then the vertices are unreachable

        if (distance == INT_MAX):

            ans.append(-1)

        

        else:

            ans.append(distance)

    

    return ans

C++ (g++ 5.4)

/*

    Time Complexity: O(V*(V+E)*log(V) + Q)

    Space Complexity: O(V^2)



    Where V and E are the number of vertices and edges in the graph and Q is the number of queries

*/



#include 

int INT_MAX = 1000000000;



class myComparator 

{

    public:



        bool operator()(vector &p1, vector &p2) 

        {

            return p1[0] > p2[0];

        }

};



vector dijkstra(vector> &graph, int n, int source)

{   

    // Dist array 

    vector dist (n + 1, INT_MAX);



    dist[source] = 0;

    

    // Maintain a Priority Queue

    priority_queue, vector>, myComparator> pq;

    

    vector visited(n + 1, 0);

    pq.push({dist[source], source});



    while (!pq.empty())

    {   

        vector l = pq.top(); 

        pq.pop();

        

        // The variable cur is the current popped vertex

        int cur = l[1];

        

        // Marking cur vertex as visited

        visited[cur] = 1;

        

        for(int index = 1; index < n + 1; ++index)

        {   

            // Checking if there is a edge between index and cur and index is not visited yet

            if (visited[index] == 0 and graph[cur][index] != -1 )

            {   

                // Checking the distance can be minimized or not

                if (dist[index] > (dist[cur] + graph[cur][index]))

                {   

                    dist[index] = dist[cur] + graph[cur][index];

                    

                    // Inserting tuple of dist[index] and index in priority queue

                    pq.push({dist[index], index});

                }

            }

        }

    }



    // Returning the dist array

    return dist;

}



vector pathQueries(int v, int e, int q, vector> &edges, vector> &queries)

{

    // Buliding adjacency matrix for the given graph

    // The graph[i][j] will be -1 if i and j are not connect by an edge

    vector> graph(v + 1, vector(v + 1 ,-1));



    for(int i = 0 ; i < edges.size(); i++)

    {   

        vector edge = edges[i];



        // Given graph is an undirected graph,so edge will be bidirectional

        graph[edge[0]][edge[1]] = edge[2];

        graph[edge[1]][edge[0]] = edge[2];

    }



    // The dis array to store the shortest distance of all pairs

    vector> dis(v + 1);



    for(int index = 1; index < v + 1; index++)

    {   

        dis[index] = dijkstra(graph, v, index);

    }



    // The ans array to store the answers of the queries.

    vector ans(q);

    

    for(int i = 0; i < queries.size(); ++i)

    {

        vector query = queries[i];

        

        int node1 = query[0];

        int node2 = query[1];

        

        // Answer for the query

        int distance = dis[node1][node2];



        // If distance is equal to INT_MAX, then the vertices are unreachable

        if (distance == INT_MAX)

        {

            ans[i] = -1;

        }

        else

        {

            ans[i] = distance;

        }

    }

    

    return ans;

}

Accepted Answer

Floyd Warshall Algorithm

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.

Space Complexity: OtherExplanation:

O(V^2), where V is the number of vertices in the graph.

The O(V^2) space is used to store the minimum distance between all pairs of vertices, and in total, there are V*V = V^2 pairs. Hence, the overall space complexity is O(V^2).

Time Complexity: OtherExplanation:

O(V^3 + Q), where V is the number of vertices in the graph, and Q is the number of queries.

For each pair of vertices, we are trying each node as an intermediate node and the number of pairs is (V)*(V). So, the time complexity will be O(V^3). We are answering Q queries, and each query takes O(1). Hence, the overall time complexity is O(V^3 + Q).

Java (SE 1.8)


/*
	Time Complexity: O(V^3 + Q)
	Space Complexity: O(V^2)
	
	Where V is the number of vertices in the graph and Q is the number of queries
*/

import java.util.Arrays;

public class Solution {

	static int INT_MAX = 1000000000;

	public static int[] pathQueries(int v, int e, int q, int[][] edges, int[][] queries) {

		// Building dist array to store the shortest distance of each pair
		int[][] dist = new int[v + 1][];
		for (int i = 0; i < v + 1; i++) {
			int distances[] = new int[v + 1];
			Arrays.fill(distances, INT_MAX);
			dist[i] = distances;
		}

		// Setting the values of weights from the edges.
		for (int i = 0; i < edges.length; i++) {
			int[] edge = edges[i];
			dist[edge[0]][edge[1]] = edge[2];
			dist[edge[1]][edge[0]] = edge[2];
		}

		// Setting dist[index][index] as 0 as the distance between same vertices is 0.
		for (int index = 1; index < v + 1; ++index) {
			dist[index][index] = 0;
		}

		// Using intermediate vertex k trying to minimize the values of all pairs
		for (int k = 1; k < v + 1; ++k) {
			for (int index1 = 1; index1 < v + 1; ++index1) {

				// The variables index1 and index2 for traversing all possible pairs
				for (int index2 = 1; index2 < v + 1; ++index2) {

					// Updating the distance
					if (dist[index1][index2] > dist[index1][k] + dist[k][index2]) {
						dist[index1][index2] = dist[index1][k] + dist[k][index2];
					}
				}
			}
		}

		// The ans array to store the answers of queries.
		int ans[] = new int[q];

		for (int i = 0; i < queries.length; ++i) {
			int[] query = queries[i];

			int node1 = query[0];
			int node2 = query[1];

			// Answer for the query
			int distance = dist[node1][node2];

			// If distance is equal to INT_MAX, then the vertices are unreachable
			if (distance == INT_MAX) {
				ans[i] = -1;
			} else {
				ans[i] = distance;
			}
		}

		return ans;
	}

}

Python (3.5)

"""

    Time Complexity: O(V^3 + Q)

    Space Complexity: O(V^2)



    Where V is the number of vertices in the graph and Q is the number of queries

"""



from sys import maxsize

INT_MAX = maxsize



def pathQueries(v, e, q, edges, queries):



    # Buliding dist array to store the shortest distance of each pair

    dist = [[INT_MAX for idx in range(v + 1)] for i in range(v + 1)]



    # Setting the values of weights from the edges.

    for edge in edges:

        

        dist[edge[0]][edge[1]] = edge[2]

        dist[edge[1]][edge[0]] = edge[2]



    # Setting dist[index][index] as 0 as the distance between same vertices is 0.

    for index in range(1, v + 1):

        dist[index][index] = 0



    # Using intermediate vertex k trying to minimize the values of all pairs

    for k in range(1, v + 1):



        for index1 in range(1, v + 1):

            

            # The variables index1 and index2 for traversing all possible pairs

            for index2 in range(1, v + 1):



                # Updating the distance

                if (dist[index1][index2] > dist[index1][k] + dist[k][index2]):

                    dist[index1][index2] = dist[index1][k] + dist[k][index2]



    # The ans array to store the answers of queries.

    ans = []



    for query in queries:

        

        node1 = query[0]

        node2 = query[1]

        

        # Answer for the query

        distance = dist[node1][node2]



        # If distance is equal to INT_MAX then the vertices are unreachable

        if(distance == INT_MAX):

            ans.append(-1)

            

        else:

            ans.append(distance)



    return ans

C++ (g++ 5.4)

/*

    Time Complexity: O(V^3 + Q)

    Space Complexity: O(V^2)



    Where V is the number of vertices in the graph and Q is the number of queries

*/



int INT_MAX = 1000000000;



vector pathQueries(int v, int e, int q, vector> &edges, vector> &queries)

{

    // Buliding dist array to store the shortest distance of each pair

    vector> dist(v + 1, vector(v + 1, INT_MAX));



    // Setting the values of weights from the edges.

    for(int i = 0; i < edges.size(); i++)

    {

        vector edge = edges[i];

        

        dist[edge[0]][edge[1]] = edge[2];

        dist[edge[1]][edge[0]] = edge[2];

    }



    // Setting dist[index][index] as 0 as the distance between same vertices is 0.

    for(int index = 1; index < v + 1; ++index)

    {

        dist[index][index] = 0;

    }



    // Using intermediate vertex k trying to minimize the values of all pairs

    for(int k = 1; k < v + 1; ++k)

    {

        for(int index1 = 1; index1 < v + 1; ++index1)

        {   

            // The variables index1 and index2 for traversing all possible pairs

            for(int index2 = 1; index2 < v + 1; ++index2) 

            {

                // Updating the distance

                if (dist[index1][index2] > dist[index1][k] + dist[k][index2])

                {

                    dist[index1][index2] = dist[index1][k] + dist[k][index2];

                }

            }

        }

    }



    // The ans array to store the answers of queries.

    vector ans(q);



    for(int i = 0; i < queries.size(); ++i)

    {   

        vector query =queries[i];

        

        int node1 = query[0];

        int node2 = query[1];

        

        // Answer for the query

        int distance = dist[node1][node2];



        // If distance is equal to INT_MAX, then the vertices are unreachable

        if(distance == INT_MAX)

        {

            ans[i] = -1;

        }   

        else

        {

            ans[i] = distance;

        }

    }



    return ans;

}

You are given a weighted, undirected graph with ‘V’ vertices numbered from 1 to ‘V’ and ‘E’ bidirectional edges.

You have to answer ‘Q’ queries. Every query has two integers, ‘u’, ‘v’, representing the vertices. Your task is to print the shortest distance between ‘u’ and ‘v’ and print -1 if there is no path.

For example:

Input Format:

Output Format:

Note:

Constraints:

Top Lido Learning Software Developer interview questions & answers

Popular interview questions of Software Developer