Swee How Tan wrote:Hi, i am new to this forum so treat me well! haha
I am doing a project which i have to load a list of flights details from a text file. I read the text file and have load the 3 values into a hashmap. The 3 values are in this format (Airport ID, To, From). The To and From are being put into a list before putting into hashmap together with the ID.
I am having trouble with finding all possible routes from a selected To and From. I have read up on Dijkstra's algorithm but i did not know how to apply this due to lack of knowledge.
Ps. I am still a student studying java :P
Henry Wong wrote:
Swee How Tan wrote:Hi, i am new to this forum so treat me well! haha
I am doing a project which i have to load a list of flights details from a text file. I read the text file and have load the 3 values into a hashmap. The 3 values are in this format (Airport ID, To, From). The To and From are being put into a list before putting into hashmap together with the ID.
I am having trouble with finding all possible routes from a selected To and From. I have read up on Dijkstra's algorithm but i did not know how to apply this due to lack of knowledge.
Ps. I am still a student studying java :P
Dijkstra's algorithm is used to find the shortest path -- not all possible paths... but to answer your question, finding all possible paths is probably best done via recursion (which I am assuming you just learned, or your instructor wouldn't give you such an assignment).
Henry
Swee How Tan wrote:I used hashmap is because that is what the teacher taught us.
So i hope if you guys can sort of give me a headstart on how am i going to find all possible routes in java. Thanks!
Swee How Tan wrote:
Actually this is counted as an advanced java feature so it was not teached. If i dont add any advanced feature, i am so going to just get a pass
Henry Wong wrote:
Swee How Tan wrote:I used hashmap is because that is what the teacher taught us.
So i hope if you guys can sort of give me a headstart on how am i going to find all possible routes in java. Thanks!
Well, as you stated...
Swee How Tan wrote:
Actually this is counted as an advanced java feature so it was not teached. If i dont add any advanced feature, i am so going to just get a pass
You are going to require lots of stuff that haven't been taught. It is actual possible to use a hashmap to implement a graph, but that will require you to basically implement a heap in that collection (so you need to understand graph theory, and some memory management). It may be easier to learn graphs, and implementing it directly, than to use a hashmap.
Henry
Jayesh A Lalwani wrote:DO you understand recursion? You can build brute force recursive algorithm that can do this using hashmaps, but to understand the algorithm, you will need to understand recursion
Swee How Tan wrote:
Jayesh A Lalwani wrote:DO you understand recursion? You can build brute force recursive algorithm that can do this using hashmaps, but to understand the algorithm, you will need to understand recursion
I sort of understand recursion but i don't see the link between recursion and finding all possible routes using hashmap. Kindly enlighten me
Henry Wong wrote:
Swee How Tan wrote:
Jayesh A Lalwani wrote:DO you understand recursion? You can build brute force recursive algorithm that can do this using hashmaps, but to understand the algorithm, you will need to understand recursion
I sort of understand recursion but i don't see the link between recursion and finding all possible routes using hashmap. Kindly enlighten me
In order to find all possible routes, you need to actually test every possible route. That means for each location, you need to test each flight from this location, and see if you can get to either the final location, or a location that isn't in the current path. At the next location, you need to do the same thing (meaning nested loop). So, you have to iterate for X number of times, and nest via a Y number of nested loops (which actually change with each iteration).
Obviously, this can't be done with a single method, so you need methods to call methods -- and when a method calls itself (either directly or indirectly), we call that recursion.
Henry
Swee How Tan wrote:
I have thought of this method by using if loop and for loop. But after serious thinking, the number of transfer might be more than 10 means i have to write alot of method to complete? So i am now researching on breadth-first algorithm.
Thanks for explaining to me
t
Swee How Tan wrote:I used hashmap is because that is what the teacher taught us.
So i hope if you guys can sort of give me a headstart on how am i going to find all possible routes in java. Thanks!
Swee How Tan wrote:This is my current code...
"Leadership is nature's way of removing morons from the productive flow" - Dogbert
Articles by Winston can be found here
Don't get me started about those stupid light bulbs. |