Find optimal path (Dijkstra or A*)
Budget: €8 – €30 EUR
Task
The task is to find the optimal path between different pairs of points in a given road network.
The input arrives at the standard input separated by tabs (\ t) and lines in the following order:
- number of node pairs between which to search for a path (p)
- number of intersections (or nodes) of the road network (n)
- number of roads (edges) in the road network (e)
- an empty dividing line
- p number of lines, each of which contains two integers separated by a tab. The first number is the ID of the starting node and the second is the ID of the destination node
- another empty separator line
- n number of lines, each of which contains two integers separated by a tab. The first number is the x coordinate of the intersection, the second number is the y coordinate of a plane. The first line describes the intersection with ID 0, and the next lines describe the intersection with ID 1.2…, respectively.
- another empty separator line
- e number of lines, each of which contains two integers separated by a tab. The two numbers indicate which intersections the given road section belongs to. All roads are two-way. The length of the path is the distance of the two endpoints.
For each of the p paths, the optimal path length path must be calculated for the specified road network.
The solution should be written to standard output. The output is a line separated by tabs containing the number p, where the numbers are the lengths of the shortest path. The result must be rounded to two decimals.
The solution is a single file, should include a Main class, including a main () function. Waits for input on standard input, writes output to standard output.
Can be written in Java or Python. In case of using Python, the interpreter is version 3.9.1, only standard libraries can be used in the solution, so Numpy, for example, can not be used.
Example:
In the example input attached, 2 routes are to be calculated, with 3 intersections and 3 edges on the map.
Route 1 is calculated from 0 to vertex ID 2.
Identifiers and coordinates of the intersections: 0: (2.0), 1: (-4.1), 2: (6.3).
The road runs between nodes 1-0, 1-2 and 0-2, with weights of 6.08, 10.20 and 5.0 respectively. (these are the calculated distances)
Output:
Since our road network in this case is a triangle, the optimal road is the direct road section between the peaks. Thus, the output for the example is as attached.
The task is to find the optimal path between different pairs of points in a given road network.
The input arrives at the standard input separated by tabs (\ t) and lines in the following order:
- number of node pairs between which to search for a path (p)
- number of intersections (or nodes) of the road network (n)
- number of roads (edges) in the road network (e)
- an empty dividing line
- p number of lines, each of which contains two integers separated by a tab. The first number is the ID of the starting node and the second is the ID of the destination node
- another empty separator line
- n number of lines, each of which contains two integers separated by a tab. The first number is the x coordinate of the intersection, the second number is the y coordinate of a plane. The first line describes the intersection with ID 0, and the next lines describe the intersection with ID 1.2…, respectively.
- another empty separator line
- e number of lines, each of which contains two integers separated by a tab. The two numbers indicate which intersections the given road section belongs to. All roads are two-way. The length of the path is the distance of the two endpoints.
For each of the p paths, the optimal path length path must be calculated for the specified road network.
The solution should be written to standard output. The output is a line separated by tabs containing the number p, where the numbers are the lengths of the shortest path. The result must be rounded to two decimals.
The solution is a single file, should include a Main class, including a main () function. Waits for input on standard input, writes output to standard output.
Can be written in Java or Python. In case of using Python, the interpreter is version 3.9.1, only standard libraries can be used in the solution, so Numpy, for example, can not be used.
Example:
In the example input attached, 2 routes are to be calculated, with 3 intersections and 3 edges on the map.
Route 1 is calculated from 0 to vertex ID 2.
Identifiers and coordinates of the intersections: 0: (2.0), 1: (-4.1), 2: (6.3).
The road runs between nodes 1-0, 1-2 and 0-2, with weights of 6.08, 10.20 and 5.0 respectively. (these are the calculated distances)
Output:
Since our road network in this case is a triangle, the optimal road is the direct road section between the peaks. Thus, the output for the example is as attached.
Related categories:
Business, Accounting, Human Resources & Legal
Python
Object Oriented Programming (OOP)