An algorithm for finding the shortest path in a graph, invented by EwDijkstra. See AstarSearch.

A definition and pseudo-code are here:

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Examples of this are here:

http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml

http://www.python.org/doc/essays/graphs.html

(Is there a better place to talk about algorithms like this?)

I've seen a Google ad for "New SPF algorithm - http://spf4routing.com - New SPF (Shortest Path First) algorithm faster than Dijkstra"

which seems to be designed for internet routers.

- Can one really patent an algorithm, as this web site implies?
- Is the algorithm they are trying to patent AstarSearch, perhaps with a nice heuristic? Or is it really significantly new -- perhaps a distributed algorithm designed to run with limited memory on any one particular router, but scalable to any number of routers?

See also:

EditText of this page (last edited August 27, 2008) or FindPage with title or text search