graphs
How can i find the shortest path between node a and b? Just a short description will do, there's no need to write code. Just to explain a little how it would work ..
Hints:
You will need to solve all possible paths, then pick the one with the shortest length.
How do you intend to store the result? Do you want just the length, or do you want the path itself?
This kind of algorithm is easiest to understand recursively.
Whether or not the graph is directed, make sure you don't revisit a node. (If you do, then you can simply discard all the paths found between the revisited node.) To do this, you will need to either "mark" visited nodes in some way (which requires an extra field in the node for just this purpose) or to keep a separate list of nodes visited.
Read more here: http://en.wikipedia.org/wiki/Shortest_path
Good luck!
You will need to solve all possible paths, then pick the one with the shortest length.
How do you intend to store the result? Do you want just the length, or do you want the path itself?
This kind of algorithm is easiest to understand recursively.
Whether or not the graph is directed, make sure you don't revisit a node. (If you do, then you can simply discard all the paths found between the revisited node.) To do this, you will need to either "mark" visited nodes in some way (which requires an extra field in the node for just this purpose) or to keep a separate list of nodes visited.
Read more here: http://en.wikipedia.org/wiki/Shortest_path
Good luck!
Last edited on
yeah i'm using a directed graph, and i'm using a set to store the visited nodes. I just want to return the value of the distance from point A to point B... the weight, not the full path... i could probably use a stack to remeber the path but i don't need that complication right now. I could show you some code i wrote.. but it's pretty stupid and doesn't work :-? . I'll just go ahead and read some more.
http://www.policyalmanac.org/games/aStarTutorial.htm
an excellent beginner documentation on pathfinding. theres also a simpler (but slower) way to do so which is called Dijkstra's algorithm which you can search up urself. hope this helps
an excellent beginner documentation on pathfinding. theres also a simpler (but slower) way to do so which is called Dijkstra's algorithm which you can search up urself. hope this helps
Topic archived. No new replies allowed.