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.

Results 1 to 3 of 3

Thread: FlightPath problem again [Using Dijkstra's Algorithm, but it's only allowed to go....

  1. #1
    Member
    Join Date
    Jan 2012
    Posts
    33
    My Mood
    Confused
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default 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?
     deleted code.
    City is just a vertex class, FlightPath is an edge class
    Last edited by CjStaal; May 9th, 2012 at 10:33 PM.


  2. #2
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,318
    Thanks
    181
    Thanked 833 Times in 772 Posts
    Blog Entries
    5

    Default Re: FlightPath problem again [Using Dijkstra's Algorithm, but it's only allowed to go

    it seems it's allowing backtracking
    I'm not sure what you mean...do you mean the edges are bidirectional?

    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

  3. #3
    Member
    Join Date
    Jan 2012
    Posts
    33
    My Mood
    Confused
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default 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

Similar Threads

  1. [SOLVED] Dijkstra's Algorithm
    By th3crack3n in forum Algorithms & Recursion
    Replies: 4
    Last Post: April 23rd, 2012, 06:18 PM
  2. Dijkstra's code help
    By csharp100 in forum What's Wrong With My Code?
    Replies: 18
    Last Post: March 24th, 2012, 08:15 PM
  3. Euler Paths with dfs algorithm problem
    By claudio.r in forum Algorithms & Recursion
    Replies: 18
    Last Post: March 22nd, 2012, 04:39 PM
  4. Is this allowed?
    By javapenguin in forum What's Wrong With My Code?
    Replies: 28
    Last Post: November 15th, 2010, 03:27 PM
  5. I have algorithm problem
    By Newoor in forum What's Wrong With My Code?
    Replies: 3
    Last Post: November 11th, 2009, 08:11 PM