访问某些节点的网格图的最短路径算法
Shortest path algorithm for a grid map which visites some nodes
我有一张网格图，我需要找到两个节点之间的最短路径，但该路径必须包含一些节点。
我想尝试所有排列，但地图大小和必须节点的数量将是可变的，所以我想使用最佳算法。
地图将类似于：
map
-Dark brown square at Y18 is the start point
-Light brown squares from B20 to S20 are the end point (can make just one end point if needed)
-White squares are walls (you cannot go through them)
-Blue squares means that the point in front of it is a must-pass (for example, the blue square at q5-q6 means must pass zone of p5-p6)
我将使用 Java，我将使该映射成为具有它们之间连接的图形（例如 s10 与 s9、o10 和 s11 连接）。
非常感谢您的帮助，如果您有任何问题，请尽管提问。
据我了解，这是两个问题的结合；你有出发点、目的地节点和强制性中间节点。为了确定最短路径，您必须计算起始节点与所有中间节点之间的距离、所有中间节点对以及每个中间节点到目的地的距离。如果仅涉及非负边权重，则可以通过 Dijkstra.
算法来完成
一旦计算出所有距离，最优的Hamiltonian path from the starting node to the destination node, where all intermediate nodes are used, has to be calculated. However, as this problem is NP-hard，很可能无法使用有效的算法求解；暴力破解所有排列可能是可行的。
渐近地，这可能无济于事，因为您仍然需要求解汉密尔顿路径，但要计算每个节点之间的距离，您可以使用 Floyd-Warshall 来加快速度。
我有一张网格图，我需要找到两个节点之间的最短路径，但该路径必须包含一些节点。
我想尝试所有排列，但地图大小和必须节点的数量将是可变的，所以我想使用最佳算法。
地图将类似于： map
-Dark brown square at Y18 is the start point
-Light brown squares from B20 to S20 are the end point (can make just one end point if needed)
-White squares are walls (you cannot go through them)
-Blue squares means that the point in front of it is a must-pass (for example, the blue square at q5-q6 means must pass zone of p5-p6)
我将使用 Java，我将使该映射成为具有它们之间连接的图形（例如 s10 与 s9、o10 和 s11 连接）。
非常感谢您的帮助，如果您有任何问题，请尽管提问。
据我了解，这是两个问题的结合；你有出发点、目的地节点和强制性中间节点。为了确定最短路径，您必须计算起始节点与所有中间节点之间的距离、所有中间节点对以及每个中间节点到目的地的距离。如果仅涉及非负边权重，则可以通过 Dijkstra.
算法来完成一旦计算出所有距离，最优的Hamiltonian path from the starting node to the destination node, where all intermediate nodes are used, has to be calculated. However, as this problem is NP-hard，很可能无法使用有效的算法求解；暴力破解所有排列可能是可行的。
渐近地，这可能无济于事，因为您仍然需要求解汉密尔顿路径，但要计算每个节点之间的距离，您可以使用 Floyd-Warshall 来加快速度。