Printable View
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 classCode :
I'm not sure what you mean...do you mean the edges are bidirectional?Quote:
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 ;)
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 :)