Travelling the graphs - Java
Budget: $30 – $250 USD
I have a graph written as a sequence of edges with associated distance (travel time), as well as a start and destination node with an associated maximum allowed travel time. All edges can be traveled both ways.
Determine the single shortest path between the start and destination, and print the route if the distance of the path is equal or less than the maximum allowed travel time.
Input Format:
Input is read from standard input and has the following characteristics:
It is two lines; the first line describes the edges of the graph
o Each edge is formatted as an opening bracket '[', the first node of the pair, a comma, the second node in the pair, another comma, the distance between the nodes, followed by a closing bracket ']'. Example: '[A,B,5].
the second line describes the start and destination node, as well as the maximum allowed travel time the starting node, followed by an ascii arrow '->(two characters), the destination node, a comma, and the maximum allowed travel time. Example 'A ->D,5
- Leading or trailing whitespace is not allowed
- All nodes are single, uppercase letters.
- Edges are separated by a single space.
- Distances are specified as unsigned integers
- The sequence of edges is not ordered in any specific way.
Output:
- It is one line.
- Contains no whitespace.
- If errors are present, print te first of below listed errors (e.g. if E1 and E2 are present, print "E1")
- If no errors are present, print the route using the representation as described below.
Errors
E1 - Input syntax error
E2 - Logical input error
E3 - Failed to find a suitable route
Logical input errors are duplicate definitions of edges, specifying either a start or destination node (second line) that is not actually defined in the graph(first line), disconnected graphs, or more than one shportest path found.
Output representation:
If there were no errors and the shortest route is found, the nodes should be printed in traveling order, including the start and destination, separated by ascii arrows '->' (two characters)
Sample Input:
[A,B,3] [B,C,5] [C,D,2]
A->D,10
Sample output:
A->B->C->D
Determine the single shortest path between the start and destination, and print the route if the distance of the path is equal or less than the maximum allowed travel time.
Input Format:
Input is read from standard input and has the following characteristics:
It is two lines; the first line describes the edges of the graph
o Each edge is formatted as an opening bracket '[', the first node of the pair, a comma, the second node in the pair, another comma, the distance between the nodes, followed by a closing bracket ']'. Example: '[A,B,5].
the second line describes the start and destination node, as well as the maximum allowed travel time the starting node, followed by an ascii arrow '->(two characters), the destination node, a comma, and the maximum allowed travel time. Example 'A ->D,5
- Leading or trailing whitespace is not allowed
- All nodes are single, uppercase letters.
- Edges are separated by a single space.
- Distances are specified as unsigned integers
- The sequence of edges is not ordered in any specific way.
Output:
- It is one line.
- Contains no whitespace.
- If errors are present, print te first of below listed errors (e.g. if E1 and E2 are present, print "E1")
- If no errors are present, print the route using the representation as described below.
Errors
E1 - Input syntax error
E2 - Logical input error
E3 - Failed to find a suitable route
Logical input errors are duplicate definitions of edges, specifying either a start or destination node (second line) that is not actually defined in the graph(first line), disconnected graphs, or more than one shportest path found.
Output representation:
If there were no errors and the shortest route is found, the nodes should be printed in traveling order, including the start and destination, separated by ascii arrows '->' (two characters)
Sample Input:
[A,B,3] [B,C,5] [C,D,2]
A->D,10
Sample output:
A->B->C->D