Welcome to the Java Programming Forums
The professional, friendly Java community. 21,500 members and growing!
The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.
>> REGISTER NOW TO START POSTING
Members have full access to the forums. Advertisements are removed for registered users.
LinkBack URL
About LinkBacks
FlightPath problem again [Using Dijkstra's Algorithm, but it's only allowed to go....
Ok, so a flight may connect Chicago to NY, but no flight from NY to Chicago [needs to go through Boston].
Here's the thing though, the algorithm I'm using right now -- it seems it's allowing backtracking. How can I modify it to work?
City is just a vertex class, FlightPath is an edge classdeleted code.
Last edited by CjStaal; May 9th, 2012 at 10:33 PM.
Related threads:
Re: FlightPath problem again [Using Dijkstra's Algorithm, but it's only allowed to go
I'm not sure what you mean...do you mean the edges are bidirectional?it seems it's allowing backtracking
If you are trying to implement Dijkstra's algorithm, I'd recommend - rather than relying on a mix-match of Map's and Set's - to create both a Node and Edge class to encapsulate the city/distance data away from the Graph and algorithm itself, which will (at least to me) makes much more sense when implementing an algorithm such as this, allow you to control directionality more directly, as well as help you abstract the algorithm and make it useful in other context (by defining the Node and Edge class with a Generic Type Definition). There are also open source libraries that will help you facilitate accomplishing your goad (for instance JUNG), that is of course you don't want to get your hands too dirty
Re: FlightPath problem again [Using Dijkstra's Algorithm, but it's only allowed to go
I was probably doing something wrong. It was allowing weird flights.
I watched a lecture from mitopencourseware dealing with Bellman Ford algorithm and implemented a modified version of that to suit my needs.
I totally re-wrote it again to allow multiple "accountants" with each path (hashmap string, accountant) and to getValue(String type) to get the weight
would return the value of whatever accountant you called (each has a name). That way I can put in the algorithm arguments
list vertex, list edge, vertex source, string type
where City=vertex and path=edge.
It's all working dandy now. 4th attempt's the charm.
Thanks for all your help
Reply With Quote