from wiki

A pathfinding method searches a graph by starting at one vertex and exploring adjacent nodes until the destination node is reached.

Two primary problems of pathfinding are (1) to find a path between two nodes in a graph; and (2) the shortest path problem—to find the optimal shortest path. Basic algorithms such as breadth-first and depth-first search address the first problem by exhausting all possibilities; starting from the given node, they iterate over all potential paths until they reach the destination node. These algorithms run in $O(|V|+|E|)$, or linear time, where V is the number of vertices, and E is the number of edges between vertices.

The more complicated problem is finding the optimal path. The exhaustive approach in this case is known as the Bellman–Ford algorithm, which yields a time complexity of $O(|V||E|)$, or quadratic time. However, it is not necessary to examine all possible paths to find the optimal one. Algorithms such as A*and Dijkstra’s algorithm strategically eliminate paths, either through heuristics or through dynamic programming. By eliminating impossible paths, these algorithms can achieve time complexities as low as $O(|E|\log⁡(|V|))$.

The above algorithms are among the best general algorithms which operate on a graph without preprocessing. However, in practical travel-routing systems, even better time complexities can be attained by algorithms which can pre-process the graph to attain better performance. One such algorithm is contraction hierarchies.

Bellman-Ford algorithm

Dijkstra’s algorithm

begins with a start node and an “open set” of candidate nodes.

At each step, the node in the open set with the lowest distance from the start is examined. The node is marked “closed”, and all nodes adjacent to it are added to the open set if they have not already been examined. This process repeats until a path to the destination has been found.

算法会找到从起始顶点到每个顶点(距离小于起始顶点到目标顶点最短路径)的最短路径.

Dijkstra’s algorithm fails if there is a negative edge weight.

A* algorithm

Sample algorithm

  1 2 3 4 5 6 7 8
X X X X X X X X X X
X _ _ _ X X _ X _ X 1
X _ X _ _ X _ _ _ X 2
X S X X _ _ _ X _ X 3
X _ X _ _ X _ _ _ X 4
X _ _ _ X X _ X _ X 5
X _ X _ _ X _ X _ X 6
X _ X X _ _ _ X _ X 7
X _ _ O _ X _ _ _ X 8
X X X X X X X X X X

  1 2 3 4 5 6 7 8
X X X X X X X X X X
X _ _ _ X X _ X _ X 1
X _ X _ _ X _ _ _ X 2
X S X X _ _ _ X _ X 3
X 6 X 6 _ X _ _ _ X 4
X 5 6 5 X X 6 X _ X 5
X 4 X 4 3 X 5 X _ X 6
X 3 X X 2 3 4 X _ X 7
X 2 1 0 1 X 5 6 _ X 8
X X X X X X X X X X