矩阵中的最短路径
我有点困惑，我有以下模式
S...*... ....*..... **...**. .G1....*. ........ ...G2**.. ........ ....*.G3D 传说的含义如下
S = source D = Destination G = point to be visited before reaching destination . = paths * = blocked path
这种方法会给我最短的路径吗？
Distance = Min((S,G1) (S,G2) (S,G3)) Distance = Distance + Min((G1,G2) (G1,G3)) // Assuming that G1 is shortest Distance = Distance + Distance(G3 , D)
G点可以随机分布，我正在使用BFS
G <15且矩阵<= 100×100
不，那不行。 这就是所谓的贪婪方法，它不会起作用，因为它可能会迫使你做一个糟糕的最后一步。
例如考虑这种情况：
S G3 G1 G2 D
-
G1最接近S，因此将首先选择。 - 然后
G2最接近G1，因此将选择第二 - 左边是
G3
即你的方法将选择G1 ， G2 ， G3而最佳解决方案是直线访问G3 ， G1 G2 。
事实上，将旅行商问题减少到这个问题是微不足道的。 只需将S和D设置为彼此相邻。 这certificate你所描述的问题是NP难的，即你做得比穷举搜索更好。
你有两张图。 首先是您的架构上的图片：
S...*... ....*..... **...**. .G1....*. ........ ...G2**.. ........ ....*.G3D
第二个是（无定向的）：
S-G1 S-G2 S-G3 SD ... G2-G3 G2-D
使用第一个图形查找第二个边缘权重。 然后任务是为第二个图找到S-*-*-*-D最短路径！