Problem: Minimum Valid Path The goal of this assessment is to use appropriate data structures and...

Transcribed Image Text:

Problem: Minimum Valid Path The goal of this assessment is to use appropriate data structures and write algorithms to solve the minimum valid path problem. The problem is to find the minimum cost of a valid path between two given vertices in a weighted directed graph with some vertices marked as special that contains exactly one special vertex and also satisfy a particular condition on the weighting of adjacent edges as explained below. This problem resembles the problem of finding a path with minimum cost to travel between two places where the path includes exactly one special place. Learning outcome Critically analyse a specific topic whilst applying the underlying principles and concepts to the field of study Task: You are given a weighted directed graph some of whose vertices are marked as special vertices. A valid path in it is a path which satisfies the following conditions: 1. For any two adjacent edges x and y on the path, 0.5*weight(x) <= weight(y) <= 2*weight(x) 2. The path contains exactly one special vertex. Given two vertices x and y, your task is to calculate the minimum cost of a valid path between them. Input Format First line: n and m, the number of vertices and the number of edges in the graph. (1≤ n s 1000, 1sm s 5000) Next m lines contain three integers u, v, and w representing an edge from vertex u to vertex V, with a weight of w. (1su, vs n, 1s w≤ 10000) Next line contains an integer k which is the number of special vertices. (15 ks n) Next line contains k distinct integers, the indices of the special vertices. (15 index ≤ n) The last line contains the integers x and y, the source and destination vertices. (1s x, ys n) Note: Graph can have multiple edges between two vertices. Output Format If there is no valid path from x toy output -1, else output the path and the minimum cost of a valid path from x to y. Sample Input 44 121 231 341 131 1 4 14 Sample Output Path: 1-3-4 Min. cost= 2 4 1 1 1 Explanation In the given sample, it is clear that path 1-3-4 is a valid path with cost 2. Though 1-2- 3-4 is also a valid path, but its cost is 3. So, 2 is the minimum cost of a valid path. Submission Submit your code and supporting Microsoft word or pdf document including screenshots of the code and brief narrative about the algorithm and utilized data structures to Moodle. You will be also required to demo your work in the class. Problem: Minimum Valid Path The goal of this assessment is to use appropriate data structures and write algorithms to solve the minimum valid path problem. The problem is to find the minimum cost of a valid path between two given vertices in a weighted directed graph with some vertices marked as special that contains exactly one special vertex and also satisfy a particular condition on the weighting of adjacent edges as explained below. This problem resembles the problem of finding a path with minimum cost to travel between two places where the path includes exactly one special place. Learning outcome Critically analyse a specific topic whilst applying the underlying principles and concepts to the field of study Task: You are given a weighted directed graph some of whose vertices are marked as special vertices. A valid path in it is a path which satisfies the following conditions: 1. For any two adjacent edges x and y on the path, 0.5*weight(x) <= weight(y) <= 2*weight(x) 2. The path contains exactly one special vertex. Given two vertices x and y, your task is to calculate the minimum cost of a valid path between them. Input Format First line: n and m, the number of vertices and the number of edges in the graph. (1≤ n s 1000, 1sm s 5000) Next m lines contain three integers u, v, and w representing an edge from vertex u to vertex V, with a weight of w. (1su, vs n, 1s w≤ 10000) Next line contains an integer k which is the number of special vertices. (15 ks n) Next line contains k distinct integers, the indices of the special vertices. (15 index ≤ n) The last line contains the integers x and y, the source and destination vertices. (1s x, ys n) Note: Graph can have multiple edges between two vertices. Output Format If there is no valid path from x toy output -1, else output the path and the minimum cost of a valid path from x to y. Sample Input 44 121 231 341 131 1 4 14 Sample Output Path: 1-3-4 Min. cost= 2 4 1 1 1 Explanation In the given sample, it is clear that path 1-3-4 is a valid path with cost 2. Though 1-2- 3-4 is also a valid path, but its cost is 3. So, 2 is the minimum cost of a valid path. Submission Submit your code and supporting Microsoft word or pdf document including screenshots of the code and brief narrative about the algorithm and utilized data structures to Moodle. You will be also required to demo your work in the class.

Answer rating: 100% (QA)

To solve the Minimum Valid Path problem you can use Dijkstras algorithm with some modifications to m... View the full answer