几天来，我一直在努力弄清楚如何实现弗洛伊德算法，以找到网格结构中的最短路径，如下所述。任何人都可以指出我将如何实现这样的事情的正确方向吗？谢谢。
输入:
- 开始/结束坐标
- 用户输入的数字必须介于 0 到 10 之间
- 障碍物数量
- 左上角和右下角的障碍物坐标
输出:
- 显示所有经过的坐标的路径
- 作为整数的距离
限制:
- 障碍不能重叠
- Start和End不能设置在矩形障碍物内
- 路径可以包括沿着矩形的边缘行进但从不穿过它们
- 路径只能水平和垂直，不能对角
- 相邻两个顶点之间的距离为1
我需要帮助生成 121x121 数组的条件。
这就是我目前所拥有的。
for(i=1;i<=n;i++) {
for(j=1;j<=n;j++) {
if( edge exists from i to j ) W[i][j] = 1;
// distance=1 if nodes are adjacent
else if ( edge does not exist from i to j ) W[i][j] = inf;
// distance=inf. if nodes do not meet
else if ( i = j ) W[i][j] = 0; // distance=0 if i=j
}
}
最佳答案
http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm 只需使用此伪代码来实现该算法(它不应该与实际的 C++ 代码有太大区别(这是一个相当简单的算法)。Wiki 链接还提供了最短路径重建算法。 您是否会考虑实现简单的呼吸优先搜索，因为您正在处理网格。 哈哈，这是我在这个论坛上的第一篇帖子:)
关于c++ - 如何实现 Floyd 算法在具有矩形障碍物的 11x11 网格上寻找最短路径？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10286121/