How to approach problem
I'm given an array that holds information of flights origins and destinations, I am trying to write a program that determines the most efficient flight schedule given a start and end location.
I've been trying to think of a way to approach this, linked lists was one idea, any help greatly appreciated
I've been trying to think of a way to approach this, linked lists was one idea, any help greatly appreciated
It's a travelling salesman problem: http://en.wikipedia.org/wiki/Travelling_salesman_problem
It depends. What exactly do you need? A 'tour' that reaches every destination, so that destination[5] is the origin to fly to destination[6], etc.? If so, that's a TSP like coder777 said. There are no efficient exact methods, so you'll have to resort to heuristics.
If all you need is the shortest path between Start and End, given a set of (origin->destination) possibilities, that's a Single-Source Shortest Path Problem, which can be solved exactly by using Dijkstra's Algorithm.
If all you need is the shortest path between Start and End, given a set of (origin->destination) possibilities, that's a Single-Source Shortest Path Problem, which can be solved exactly by using Dijkstra's Algorithm.
Dijkstra's Algorithm is based mainly around distance between nodes yes? I'm looking for a way to find the least number of "stops" if that make sense. Would I be able to modify Dijkstra's method to solve for this?
Topic archived. No new replies allowed.