如何判断两个按Dijkstra算法在二维矩阵中移动的人员是否会相遇

我们可以根据是否允许多条最优路径选择，用两种不同的方案实现，逻辑都不复杂： #

固定最优路径场景（两人都严格走已算出的唯一最优路线） #

直接用双指针同步遍历法即可，时间复杂度极低：

• 先导出两人的最优路径步骤序列，分别记为path_a、path_b，序列的第k个元素对应两人走了k步之后所在的坐标
• 取两个序列的最大长度作为遍历上限，从第0步（起点位置）开始逐次比对相同步数下两人的坐标：
  • 若某一步两个坐标完全一致，说明两人同时抵达同一节点，判定相遇
  • 额外补充交错判定：如果第k步A在坐标p、B在坐标q，第k+1步A移动到q、B移动到p，说明两人在相邻节点对向移动擦肩而过，也属于途中相遇
• 整个遍历过程只需要走最多几十到上百次（取决于矩阵大小），计算成本可以忽略

多最优路径场景（两人各自有权重相同的多条最优路线可选） #

如果需要判断「是否存在任意一种最优路线选择，使得两人途中相遇」，可以用*状态级BFS（广度优先搜索）*处理：

• 定义单步状态为(A当前坐标, B当前坐标, A累计权重, B累计权重)
• 初始状态为(A起点坐标, B起点坐标, 0, 0)
• 每轮状态扩展时，A、B同步各走一步到合法的相邻节点，只要两人的累计权重都不超过各自Dijkstra算出的最短路径总权重，就属于合法状态，可以加入队列继续扩展
• 扩展过程中只要出现A、B坐标相同的状态，就可以直接判定存在相遇可能
• 可以加去重逻辑：记录已经遍历过的(A坐标, B坐标, A累计权重, B累计权重)组合，避免重复计算浪费资源

如果你的判定规则是「无论两人选哪条最优路线，都一定会相遇」，只需要把逻辑反过来：遍历所有合法的最优路径组合，只要存在任意一种组合全程不相遇，就可以判定为不会必然相遇。

内容的提问来源于stack exchange，提问作者fardown