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

-2

我必须编写一个模拟程序，我需要一种方法来找到从一个位置到另一个位置的最短路。此方法仅获取起始位置和最终位置，并返回代表位置之间最短路段的位置列表。事情是这样的：用Dijkstra算法寻找最短路的方法

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

我怎样才能做到这方法的Dijkstra算法的实现？

来源

2013-04-27 abea

你的问题是非常模糊的，请更具体。你有什么道路数据？你有什么尝试？码？你有没有看过a *算法？ – 2013-04-27 19:14:36

我有一个二维整数数组。是类属性，因此该方法可以使用它。我刚刚开始编写代码...启发式算法对我来说太高级了！ – abea 2013-04-27 19:30:30

不清楚你问的是什么 - BFS是一个解决方案。有很多方法可以加快搜索速度（如答案中提到的A *），但看起来您还需要其他的东西。你是否在寻找更简单的蛮力BFS？ – 2013-04-27 19:39:49

你应该查找A* search algorithm，这是一个广度优先搜索算法与启发式使其更快。

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

不过，有一点需要注意的是，你的启发式功能（在两个节点之间的成本/距离的猜测）决不小于给定的节点之间的实际成本。如果启发式函数产生的结果较小，那么A *算法不一定会找到最佳/最短/成本最低的路径。

现在，如果你想要一些很好的动画（特别是关于A *和Dijkstra算法之间的差异），那么在维基百科上进行搜索，在相应环境中执行相应算法的动画动画。从他们那里很容易知道，A *算法更好。

来源

2013-04-27 19:14:19 feralin

我只是开始编码...启发式对我来说太先进了！ – abea 2013-04-27 19:25:45

@abea那么，我会描述这是什么意思，但是，真的，只是看看算法。这并不难。 – feralin 2013-04-28 14:44:52

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

来源

2013-04-27 19:36:20 Stipo

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

回答

相关问题