• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Finding all possible routes in java.

 
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Marshal
Posts: 79177
377
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Welcome to the Ranch

Please write down Dijkstra's algorithm and let's see if we can't turn it into pseudocode.
 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I have not started on that algorithm yet as i do not know how to start.

This is my current code which will print out all direct flight and flight that have 1 transfer point.
 
Swee How Tan
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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



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
 
Author and all-around good cowpoke
Posts: 13078
6
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think you got off on the wrong foot by thinking Hashmap.

My motto is draw first, program later. Get a piece of paper or whiteboard and draw nodes for airports with flights for links


Personally I would create a custom class to represent an airport "node" - much easier to think about the problem that way.

Bill

 
Rancher
Posts: 2759
32
Eclipse IDE Spring Tomcat Server
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If you know how to build a directed graph and know how to walk through the graph, then it would be pretty trivial to build something like this. The question is how much do you know about graphs? I wouldn't take this on until I was comfortable with graph theory.

Sounds like this is for extra credit, and hence might be more difficult than your course material. Personally, I wouldn't take extra credit work without looking for all ways I can get extra credit with minimum of effort
 
Swee How Tan
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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!
 
Henry Wong
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
 
Swee How Tan
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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



OK! I think i will try research on graph but do you have any good website to learn that from? Because time is of an essence here. Thanks!
 
Jayesh A Lalwani
Rancher
Posts: 2759
32
Eclipse IDE Spring Tomcat Server
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
 
Campbell Ritchie
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
As you go through al the possible nodes, you can recursively test whether a node has been used already; if so you try the next node. If no nodes are accessible from your current location, you need to backtrack and try again.
 
Henry Wong
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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



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
 
Henry Wong
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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




That's the point of recursion. With recursion, your method can handle any flight along the path, and your method calls itself for the next flight of the path. You only have to write one method -- albeit, it is a bit more complex.

Henry
 
Jayesh A Lalwani
Rancher
Posts: 2759
32
Eclipse IDE Spring Tomcat Server
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Writing it mathematically


Route(to, from) = Route(to,layover) + route(layover,from)


So, let's say you write a funtion route that takes to and from as parameters, and returns a list of routes. So, you could do soemthign like this



The trick is that you don't want to go in circles. So, once you have visited a city you don;t want to want to visit it again. So, tyou need to keep track of which cities you visited already.
 
William Brogden
Author and all-around good cowpoke
Posts: 13078
6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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!



But your hashmap represents flight / routes / links between nodes and the problem is stated in terms of nodes (locations) - finding all routes between them.

Bill
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Swee How Tan wrote:This is my current code...


Swee How,

Please DontWriteLongLines (←click). I've broken yours up this time, but it makes your thread (not to mention your code) very hard to read. Remember, 80 characters per line.

Thanks.

Winston
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic