For a graph of N nodes with O(N) connections between nodes and positive edge-weights: Storing the shortest path between any two nodes take N^2 space. An easy implementation is "for each node, store a map from (target node) to (next step to get to target node)". Calculating the shortest path between any given two nodes takes N^2 time (Dijkstra). A* has a heuristic that can improve Dijkstra, especially for short routes. If the heuristic used is accurate within O( d log(d) ), then A* is polynomial in the length of the shortest path. Floyd–Warshall's allows you to compute all shortest paths in a graph in O(N^3) time. Johnson's allows you to compute all shortest paths in a graph in O(N^2 log N) time. Another option is "shotgun hill-climbing": generate many bad solutions, improve the bad solutions locally until you have an optimal route. ... Miss any key algorithms to solve this problem?

Quote: Miss any key algorithms to solve this problem?

That's about it for arbitrary graph pathfinding with no need to recompute, quick-start, or coordinate. There's Bellman-Ford, of course, but you specified nonnegative edge weights. More practical and widely used pathfinding algorithms generally require a bit more structure from the problem.

Oh, and I've never heard of using hill-climbing with random restart to do pathfinding.

Quote: More practical and widely used pathfinding algorithms generally require a bit more structure from the problem.

Such as?

I've heard of hierarchical A*.

Quote: That's about it for arbitrary graph pathfinding with no need to recompute, quick-start, or coordinate. There's Bellman-Ford, of course, but you specified nonnegative edge weights.

*nod* -- I figure, in most games, you don't have routes that take negative time. :)

[Edited by - NotAYakk on September 8, 2007 1:39:31 PM]

Quote: Original post by NotAYakk

Quote: More practical and widely used pathfinding algorithms generally require a bit more structure from the problem.

Such as?

I've herd of hierarchical A*.

That's a big one. Also border-following, potential fields, and other related things that work in cartesian spaces without overly complicated obstacles.

Quote: in most games, you don't have routes that take negative time. :)

You'd be surprised! Giving a bonus to certain edges (by decreasing the cost) can be useful for various things, like encouraging an agent to stay under cover or pick up items on his way to a goal.

There are lots of variations on A* that do things like use less memory. It might be best to just put all the positive edge graph search algorithms in one category. There are also different heuristics that can be used for pathfinding. Hierarchical A* is really using a hierarchy of graphs to compute heuristics for more detailed graphs, if I remember correctly. Or maybe that's something else, I don't know.

There's also IDA* (Iterative Deepening A*) that searches to a particular depth, if the target is not found it restarts the search but to a deeper level. This eliminates the need for open and closed lists of A*.

And, Fringe Search, which is somewhere between A* and IDA*. It follows the same premise as IDA* but rather than restarting the entire search, it starts just at those most recently expanded fringe nodes.

-Kirk

Distance Transform for single-target, all-source (for the uninitiated, it's basically brute force flood-fill).