javascript - 使用 dijkstra 算法检查两个人在遍历图形时是否会相遇的算法是什么？

Question

想象一下 2 个人在 2D 矩阵中从两个不同的起点开始。它们在遍历矩阵时也会有单独的端点。从两点遍历具有相应的难度（权重）。使用 Djikstra 的算法，我们可以确定两个人到达目的地的最佳路线。假设一个人一次只能移动到一个节点并且两个人同时移动，那么确定他们在遍历矩阵时是否会相互碰撞的好算法是什么？

标签： javascriptalgorithm

Answer 1

当您从两个初始顶点执行两次 Djikstra 搜索时，您更新dist[]和prev[]数组（查看Wiki 伪代码）

添加额外的数组steps[]（用于边数的距离），当您修改时 prev[v] ← u，也使steps[v] = steps[u] + 1

当您通过反向迭代读取最短路径时，比较两条路径的交点是否包含相同的值steps

例如，您发现路径在顶点 3 和 7 相交。但是A_steps[3] = 3, B_steps[3] = 2- 所以人们在不同的时刻穿过这个单元格。而如果A_steps[7] = 6, B_steps[7] = 6意味着人们确实在第六步在这个节点相遇。