c# - 用 Dijkstra 算法找到最短道路的方法

Question

我必须编写一个模拟代码，我需要一种方法来找到从一个位置到另一个位置的最短路径。此方法仅获取起始位置和最终位置，并返回代表位置之间最短路径的位置列表。像这样的东西：

public List<Tuple<int, int> ShortestRoad(Tuple<int,int> start, Tuple<int,int> end, int[,] park)
{//Code}

我怎样才能为这个方法做一个 Dijkstra 算法实现？

Answer 1

您应该查找A* 搜索算法，这是一种具有启发式的广度优先搜索算法，可以使其更快。

本质上，A* 算法是像 Dijkstra 算法一样的广度优先搜索，但它使用启发式算法，或者猜测最短路径是什么（你可以说是一个提示，告诉 A* 算法哪些节点更好看）。启发式的使用可以使 A* 算法比 Dijkstra 算法快得多，因为它通常不像 Dijkstra 算法那样查看几乎那么多的节点。

但是，需要注意的一件事是，您的启发式函数（对两个节点之间的成本/距离的猜测）绝不能小于给定节点之间的实际成本。如果您的启发式函数产生的结果较小，则 A* 算法不一定会找到最佳/最短/成本最低的路径。

现在，如果你想要一些漂亮的动画（尤其是关于 A* 和 Dijkstra 算法之间的差异），然后在 Wikipedia 上搜索两者，其中将有各自算法的动画，在两个动画之间的相同环境中执行。从他们那里很容易看出 A* 算法更好。

Answer 2

看看 Dijkstra 的最短路径算法：http ://en.wikipedia.org/wiki/Dijkstra%27s_algorithm