Last Updated: 5 Dec, 2020
Roads
Easy
Asked in companies
You live in the country with ‘V’ cities that have ‘E’ roads. You are in city ‘S’ with a car having ‘P’ amount of petrol in it. Roads are bidirectional and consume your petrol. Each road has a description ‘X’, ‘Y’ and ‘Z’, which means city ‘X’ and ‘Y’ have a road between them which consumes ‘Z’ amount of petrol. You want to visit the city ‘D’. Your task is to check if it's possible to visit ‘D’ from ‘S’ using ‘P’ amount of petrol.
For Example:
In the given graph, if we want to reach from node 1 to node 4 with ‘P’ = 10, then our answer is ‘Yes’ because there exists path 1 -> 3 -> 4, which takes 7 amount of petrol, which is less than the given value of ‘P’ so it is possible and hence, the answer is ‘Yes’.
Input Format:
The first line of the input contains a single integer, 'T,’ denoting the number of test cases.
The first line of each test case contains three space-separated integers, ‘V’, ‘E’, and ’P’, denoting the number of vertices, the number of edges in the graph, and the amount of petrol in the car.
The next ‘E’ lines of each test case contain three space-separated integers, ‘X’, ‘Y’ and ‘Z’, denoting the vertices which are connected with a bidirectional edge, and the weight of the edge.
The last line of each test case has two space-separated integers, ‘S’ and ’D’, representing the source and destination vertices.
Output Format:
For each test case, print “Yes” if there exists a path from vertex 'S’ to 'D’ which consumes less than or equal to the given amount of petrol ‘P’. Otherwise, print “No” (without quotes).
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 <= 10
2 <= V <= 2000
0 <= E <= (V*(V-1)) / 2
0 <= X,Y < V
1 <= Z <= 10 ^ 6
1 <= P <= 10 ^ 9
0 <= S,D < V
Time Limit: 1 sec
Approaches
In this approach, we will calculate the shortest path between all pairs of vertices 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 we try to find the shortest distance of a pair of vertices using an intermediate vertex whose value is already calculated as -:
distance[index1][index2] = min(distance[index1][index2], distance[index1][k] + distance[k][index2])
Where k is the intermediate vertex.Algorithm:
- Floyd Warshall Algorithm:
- Make an array distance of size (V)*(V) 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 0 to V - 1.
- set distance[index][index] as 0 (distance between same vertices is 0).
- Set the values of the edge weights into distance from the given edges.
- Using each vertex from 0 to V - 1 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 0 to V - 1.
- Set distance[index1][index2] as the minimum of distance[index1][index2] and distance[index1][k] + distance[k][index2].
- For a pair between index1 and index2, we are trying to minimize its minimum distance using intermediate vertex k. We will iterate k from 0 to V - 1.
- Values of the Shortest distance between each pair are calculated.
- Return True if the value of distance[S][D] (Shortest distance between S and D) is less than or equal to P. Otherwise, return False.
We will run the Dijkstra Algorithm for vertex S and store the minimum distance of all vertices from vertex S in an array in this approach. Then we can return the shortest distance between S and D.
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,V, S,D) where the graph is the given graph,V is the number of vertices in the graph, and S is the source vertex.
- Create an array distance with size V to store the minimum distance of all vertices from S.
- Initialize all its values with maximum integer value because at the beginning. We assume that all vertices are unreachable.
- Set distance[S] as 0.
- We will now create a min-priority queue in which we will insert elements in the form of a tuple consisting of distance from S and 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 [distance[S],S] 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 distance[index] is greater than distance[cur]+graph[cur][index], then set distance[index] as distance[cur] + graph[cur][index] and insert [distance[index],index] into the priority queue.
- The minimum distance of all vertices from the S is calculated, return the distance[D].
- Make an adjacency list of the graph named graph from the given edges(edge weight will be the one.)
- Call the function dijkstra(graph,V, S,D) and store the output. If the obtained value is less than or equal to P, return true. Otherwise, return false.