这次Dijkstra的路径发现再次出现问题
我在不同的网站上阅读过Dijkstra及其应用程序 . 它主要针对Graph进行了解释，并找出了源节点中所有节点的最短路径 .
我无法弄清楚如何使用Dijkstra在网格上寻找路径，如Wikipedia picture所述 .
因为在网格上我们有一个目的地，我们必须从源头找出它的最短距离 . 我无法将它与Dijkstra的图表联系起来 . 没有瓷砖被标记为INFINITY或将距离与其他路径/节点进行比较 .
简而言之，我们如何使用Dijkstra在网格中找到一条路径，使用定义了该算法的实际图算法 . 我们是否像BFS一样继续称它为Dijkstra's网格，还是有区别？因为我无法弄明白：/
谢谢 ：）
1 回答
为了在网格中应用dijkstra算法，不需要任何修改，因为网格是一个图形，其中节点（单元格）具有4/8个子节点（取决于您的连接性），它们是邻居 . 因此，您所要做的就是：选择您的根节点（从哪里开始），为其赋值0然后评估4/8个邻居，使用仅为1的成本（如果对于4个对等邻居，则使用sqrt（2）你正在使用8连接） . 必须将此根节点标记为已访问，并将评估的邻居标记为打开 . 然后，您选择具有最小值的已评估节点（单元格）（在这种情况下，所有节点都具有值1），因此您可以选择其中任何一个 . 将邻居添加到打开列表时，会发生其中一些neigbors已经被访问过，所以你只需忽略它们 . 如果已经在打开列表中，则重新计算它们的值，如果它们未被访问，则计算它们的值并将它们添加到打开状态，并将当前节点标记为已关闭 .
实际上，您将看到与您为图形阅读的通用Dijkstra算法完全没有区别 .
注意：为了在获得开放列表的最小值时有效，建议使用堆（通常是二进制堆），而不是在每次迭代时沿所有开放节点运行min函数 .