This isn't a "Give me the script please" request, but more of a...
What would I tell the computer to do so I get this result.
Basically I'm writing a quick web-based form that will give the quickest route between two nodes.
Each node is linked to eight others, and there are 16 nodes in total.
I'm looking to create a program that, when given the name of starting and ending nodes, would display the quickest way through the nodes, listing the name of each node.
There is no travel time between the nodes, I just need the shortest amount of nodes to travel between.
Planning on writing this in Javascript, as it's the language I know.
Basically, without writing the actual code for me (I can do that myself) how would I go about getting the computer to navigate all possible different ways through the "map" and then select the shortest route?
More of a logic puzzle than programming puzzle I guess, but this board suits.
Though I'm not sure I completely understand your problem.. I think what you need is dijkstra's pathfinding algoritm. Given a vertex in a graph it's able to find the shortest path to any other vertex. In your case you have a graph with a weight of 1 on each of the edges. It seems very lazy of me to hand you a wikipedia link but it contains some decent pseudocode.
In itself the algoritm is used to calculate the lenght of the shortest path, however you'll need the path itself as well. However it is fairly easy to save the path underway as well.
Name:
Anonymous2008-05-12 16:42
The length of the path isn't a problem, but the amount of nodes inbetween it, I can't get it around my head how to get the computer to check all routes possible, and then display the one with the shortest route.
Name:
Anonymous2008-05-12 16:47
Dijkstra's algoritm runs through all possible routes and finds the shortest, while running through the algoritm you allow each vertex to save a reference to the vertex 'behind it' (behind it meaning the shortest path back). Follow these vertex back to the original vertex and you'll have the shortest path vertex for vertex (actually you'll have them in reverse order but that shouldn't be a problem).
i'd have to agree with >>8 and speak out against dijkstra. implementing dijsktra is going to be waaay to much work for a noob like you; start with a http://en.wikipedia.org/wiki/Breadth-first_search and if it doesn't work you can optimize (but you'll have learned something in the meanwhile)
YOU WILL NOW THINK OF THE GAME WHENEVER YOU VISIT /prog/
Yeah, don't listen to these guys. Breadth-first is far too easy to be a worthwhile algorithm. And you'll have to do it every time somebody requests the path. Can your servers handle searching through up to 16 nodes every time someone requests a shortest path? I don't think so.
So what you'll need to do is run Floyd-Warshall on your graph, and fill in the results in a precomputed table. Do some work up front, then cruise past your competitor path-finding sites as they crumble under their load.
parent[i] = -1 for all i
queue.push(end)
while(queue.top() != start) {
cur = queue.pop()
foreach node in neighbours(cur) {
if (parent[node] == -1) {
queue.push(node)
parent[node] = cur
}
}
}
// prints path
cur = start
while(cur != -1) {
print cur
cur = parent[cur]
}