flightpaths, finding lowest cost -- lowest amount of crossovers

• May 7th, 2012, 11:03 PM
CjStaal
flightpaths, finding lowest cost -- lowest amount of crossovers
I have a college assignment.
I already have it working with a depth first search on the data structure [it's not a tree since there are loops]
Basically, the professor just wants the program to find A path and the price of said path.
I have that basically worked out. But I want to bring it a step further and offer "Lowest total price" option
and "lowest amount of crossover flights" and perhaps if I'm feeling up to it "lowest total price" although that would use
the same algorithm for the lowest total price.
Basically, I was thinking about using iterative deepening depth first search but I heard that's only usable on data trees.
What algorithm would I need to implement.?
Basically what I have now:

City class
--String of name
--Hashmap of cities that it connects to, price per connection
--getname()
--getDestMap()
--depthFirstSearch(City start, goalfunction isGoal, stack<City> result)
Goalfunction is an interface

Main class
--hashmap of cities and theyre name

scanner
Code java:

`CODE REMOVED Since it's not needed anymore`
• May 8th, 2012, 12:21 AM
helloworld922
Re: flightpaths, finding lowest cost -- lowest amount of crossovers
Try looking at Dijkstra's Algorithm.
• May 8th, 2012, 12:33 AM
CjStaal
Re: flightpaths, finding lowest cost -- lowest amount of crossovers
That's exactly what I need! Thanks so much!! My "Graph" would be the hashmap I have in the main class? I've encapsulated it to be its own class.
Here's the entire code

Code java:

`deleted code since it's no longer needed`

The algorithm would work with the finding lowest cost, finding lowest time
and if I set all distances to "1" it will find lowest amount of hops, correct?
Would there be a faster algorithm to find the latter of the 3 situations?

City.java would be the vertex class, and FlightInfo.java's hashmap would be the graph?
• May 8th, 2012, 12:44 AM
helloworld922
Re: flightpaths, finding lowest cost -- lowest amount of crossovers
Sounds right to me. There are other path-finding algorithms you can investigate, but they're all more or less based off of Dijkstra's algorithm with some sort of heuristic, or guess strategy.
• May 8th, 2012, 01:47 AM
CjStaal
Re: flightpaths, finding lowest cost -- lowest amount of crossovers
I've looked up examples online of the algorithm, and I've decided to rework the entire project, AGAIN lol. Well, It's going to be right this time.