Imagine 2 people starting a two different starting points in a 2D matrix. They would also have separate end points when they traverse the matrix. Traversing from two points has a corresponding difficulty (weight). Using Djikstra's algorithm, we can determine what would be the best route to take for both person to reach their destination. Given that a person can only move to one node at a time and both persons move simultaneously, what would be a good algorithm to determine if they would bump to each other as they traverse the matrix?

CodePudding user response：

When you perform two Djikstra's searches from two initial vertices, you update dist[] and prev[] arrays (looking at Wiki pseudocode)

Add additional array steps[] (for distance in number of edges), and when you modify prev[v] ← u, also make steps[v] = steps[u] 1

When you read shortest path by reverse iterations, compare if vertices of intersection of two paths contain the same value in steps

For example, you found that paths intersect in vertices 3 and 7. But A_steps[3] = 3, B_steps[3] = 2 - so persons walk through this cell in differen moments. And if A_steps[7] = 6, B_steps[7] = 6 means that persons do meet in this node at the sixth step.