GameDev.net Posting Guidelines (please read before posting)
Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.
Posted 26 October 2003 - 05:11 AM
Posted 26 October 2003 - 05:41 AM
Posted 26 October 2003 - 08:20 AM
Posted 26 October 2003 - 12:19 PM
Posted 26 October 2003 - 12:39 PM
quote:
Original post by Ziphnor
If your solution claims to find a solution to 3 or 4, then i think you have a problem when you say finding the second best path between a and b is simple. If you remove the edge (a,b) and find the best path from a -> b, then you might have a new path of the same weight as the edge (a,b), and i dont see how else you will find the second best path.
Posted 26 October 2003 - 04:19 PM
Posted 26 October 2003 - 08:26 PM
quote:
Original post by superpigquote:
Original post by Ziphnor
If your solution claims to find a solution to 3 or 4, then i think you have a problem when you say finding the second best path between a and b is simple. If you remove the edge (a,b) and find the best path from a -> b, then you might have a new path of the same weight as the edge (a,b), and i dont see how else you will find the second best path.
Well, I think that in any situation you'll end with a set of paths (i.e. more than one) for each total length.
You process every possible route through the network, and add it to the group. You pick any route from the shortest group as your optimum path. Any route from the same group can be called an 'alternate' route; any route from the next group up can be called the 'second best' route.
The most efficient solution would be one which eliminated all those 'alternate' routes in each group, I think. I'm not sure how you can 'predict' the length of a path - and thus skip it - until you've actually calculated it, though, so you'd end up processing all paths.
Though, as far as finding all paths goes, Dijikstra's can help with that. The labelling system means that you pick a single start node and process the entire network, so you can get the shortest route from any given node to all other nodes by only labelling the network once for that given node. The time would thus be O(nD(n)) where n is the number of nodes and D(n) is the time taken by Dijikstra's to label n nodes.
Richard "Superpig" Fine
quote:
BTW, is the path a-b-c-d-e-g-f-g (note the repeated g) valid as a path from a to g?
Posted 26 October 2003 - 09:28 PM
Posted 26 October 2003 - 09:36 PM
quote:
Original post by Ziphnor
If your solution claims to find a solution to 3 or 4, then i think you have a problem when you say finding the second best path between a and b is simple. If you remove the edge (a,b) and find the best path from a -> b, then you might have a new path of the same weight as the edge (a,b), and i dont see how else you will find the second best path.
Posted 26 October 2003 - 09:40 PM
Posted 26 October 2003 - 09:46 PM
Posted 27 October 2003 - 05:53 AM
quote:
I'm assuming here that an alternative path than the one given by Djikstra, but with the same weight, qualifies as a 2nd-best path. (Technically it's 1st equal, but I am assuming that calling it 2nd would be what is desired by cryo75.)
Posted 28 October 2003 - 12:55 AM
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.
GameDev.net™, the GameDev.net logo, and GDNet™ are trademarks of GameDev.net, LLC.