用Dijkstra算法寻找最短路径的方法

本文关键字：方法 最短路径 寻找 Dijkstra 算法 | 更新日期: 2023-09-27 18:11:04

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

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

我如何做一个Dijkstra算法实现这个方法?

用Dijkstra算法寻找最短路径的方法

你应该查阅A*搜索算法，这是一种宽度优先搜索算法，带有启发式，以使其更快。

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

然而，需要注意的一件事是启发式函数(两个节点之间的成本/距离的猜测)绝不能小于给定节点之间的实际成本。如果你的启发式函数产生的结果比a *算法更小，那么它不一定会找到最佳/最短/成本最低的路径。

现在，如果你想要一些漂亮的动画(特别是关于A*和Dijkstra算法之间的差异)，然后在维基百科上搜索，那里将有各自算法的动画，在相同的环境中在两个动画之间执行。很容易看出，A*算法更好。

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

相关文章：