Really need help with shortest path algorithm and graphing
I have an assignment where you're supposed to read in a file that looks like this:
SFA SLC 700 59
SFO LV 420 39
LAX LV 231 23
LV SLC 362 29
LAX SFO 344 39
LAX SLC 581 57
SFA SFO 679 67
SFO SLC 605 19
PHX DEN 586 65
LV PHX 256 21
DEN SFA 1026 72
DEN LAX 844 69
SLC DEN 379 49
SLC SJC 585 29
SJC SFO 51 19
Where the first 3 letters are source airports, the second 3 letters are destination airports, the first number is the mileage for the trip, and the second number is the price of the flight.
I'm then supposed to store this in a graph and use the shortest path algorithm (I guess) to post the cheapest flights for all possible destinations from a source airport that the user enters.
This is the last assignment of the semester and for some reason it just isn't clicking with me at all. I've looked up a whole bunch of ways to make weighted, directed graphs and they seem to make sense but I guess what's tripping me up is that there's more info that needs to be stored in this graph than just the integers that I've seen put into other peoples' graphs.
What is the best way to go about this? What kind of graph should I use? I'm definitely not understanding the shortest path algorithm, either. Maybe that would become easier to get once I have a working graph but I don't get how I'm supposed to be using it. I know it's a lot of questions but any help would be greatly appreciated. I've been able to do all the other assignments for this class pretty easily but I've worked on this one for 2 days and I feel like I'm not getting anywhere.
SFA SLC 700 59
SFO LV 420 39
LAX LV 231 23
LV SLC 362 29
LAX SFO 344 39
LAX SLC 581 57
SFA SFO 679 67
SFO SLC 605 19
PHX DEN 586 65
LV PHX 256 21
DEN SFA 1026 72
DEN LAX 844 69
SLC DEN 379 49
SLC SJC 585 29
SJC SFO 51 19
Where the first 3 letters are source airports, the second 3 letters are destination airports, the first number is the mileage for the trip, and the second number is the price of the flight.
I'm then supposed to store this in a graph and use the shortest path algorithm (I guess) to post the cheapest flights for all possible destinations from a source airport that the user enters.
This is the last assignment of the semester and for some reason it just isn't clicking with me at all. I've looked up a whole bunch of ways to make weighted, directed graphs and they seem to make sense but I guess what's tripping me up is that there's more info that needs to be stored in this graph than just the integers that I've seen put into other peoples' graphs.
What is the best way to go about this? What kind of graph should I use? I'm definitely not understanding the shortest path algorithm, either. Maybe that would become easier to get once I have a working graph but I don't get how I'm supposed to be using it. I know it's a lot of questions but any help would be greatly appreciated. I've been able to do all the other assignments for this class pretty easily but I've worked on this one for 2 days and I feel like I'm not getting anywhere.
> What kind of graph should I use?
A weighted adjacency matrix would be the simplest representation.
http://cpsc.ualr.edu/srini/DM/chapters/review5.3.html
> I'm definitely not understanding the shortest path algorithm, either.
Dijkstra's algorithm should be adequate for this.
http://cpsc.ualr.edu/srini/DM/chapters/review5.3.html#Dijkstra Alg
A weighted adjacency matrix would be the simplest representation.
http://cpsc.ualr.edu/srini/DM/chapters/review5.3.html
> I'm definitely not understanding the shortest path algorithm, either.
Dijkstra's algorithm should be adequate for this.
http://cpsc.ualr.edu/srini/DM/chapters/review5.3.html#Dijkstra Alg
Topic archived. No new replies allowed.