Pathfinding-algorithm...

[Thomas Nyberg]

Hi,

Does any1 know where I can find some good docs and tutorials about the
"A*-algorithm" or the Djikstra (hmm...something like that anyway)? I've
searched but not found anything good...

Thanks in advance,

Thomas

[dfro...@mindspring.com]

I saw some references on the net a while back but can't remember them.
You might try asking in Alt.games.development.programming.algorithms

[Martin Casado]

Thomas Nyberg (thomas...@usa.net) wrote:
: Hi,
:
: Does any1 know where I can find some good docs and tutorials about the
: "A*-algorithm" or the Djikstra (hmm...something like that anyway)? I've
: searched but not found anything good...

You'll find Dijkstra's algorithm in any CS Algorithms book. It is the most commen shortest path algorithm.

-M
:
: Thanks in advance,
:
: Thomas
:

[Stuart Anderson]

This is a version of the Dijkstra shortest path algorithm from Computer Algorithms, p245, 250 Horowitz, Sahni,
Rajaskaran ISBN 0-7167-8316-9
The following is pseudocode that resembles C and Pascal

Algorithm ShortestPaths(v,cost,dist,n)
// dist[j], 1<= j<= n, is set to the length of the shortest
// path from the vertex v to vertex j in a digraph G with n
// vertices. dist[v] is set to zero. G is represented by its
// cost adjacency matrix cost[1:n,1:n].
{
for i := 1 to n do
{// Initialise S.
S[i] := false; dist[i] := cost[v,i];
}
S[v] := true; dist[v] := 0.0; // Put v in S.
for num := 2 to n-1 do
}
// Determine n-1 paths from v.
Choose u from among those vertices not
in S such that dist[u] is minimum;
S[u] := true; // Put u in S.
for (each w adjacent to u with S[w] = false) do
// Update distances
if (dist[w] > dist[u] + cost[u,w])) then
dist[w] := dist[u] + cost[u,w];