This is an implementation of two algorithms for searching paths in a graph: UCS (Uniform Cost Search) and IDA* (Iterative Deepening A*). This project accepts as input the roads of a city, their cost to traverse under normal traffic and traffic predictions for a specific day and it calculates the less costly path between two points of the city using both algorithms.
You can find more information on the Internet about UCS and IDA*. Note that the heuristic function for IDA* in this implementation is the result of Dijkstra's algorithm using low traffic costs for all roads.
Requirements: You need to have JDK and make installed.
Execute the following commands to download and compile the code:
$ git clone https://github.com/iapost/ucs-ida
$ cd ucs-ida
$ make
For testing purposes, three files with sample inputs are provided in the examples folder. To execute the code with one of the sample inputs execute the following:
$ java Main < examples/sampleInput1.txt
The implementation reads data from standard input. The format of the data must be the following:
<Source>Node1</Source>
<Destination>Node132</Destination>
<Roads>
Road1; Node1; Node2; 44
Road2; Node2; Node5; 9
...
</Roads>
<Predictions>
Road1; normal
Road2; low
Road3; heavy
...
</Predictions>
The first two lines of the input specify the source and destination. Then, each line between <Roads> and </Roads> specifies a road with its name, its two ends and its traversal cost under normal traffic. Note that all roads are considered two-way. Finally, each line between <Predictions> and </Predictions> specifies the predicted traffic of a road for each day ("low" means 10% reduction and "heavy" means 25% increase in the cost).
Distributed under the GPL-3.0 License. See LICENSE for more information.