Блог

Представьте, что 2 человека начинают с двух разных начальных точек в 2D-матрице. У них также будут отдельные конечные точки при пересечении матрицы. Переход из двух точек имеет соответствующую сложность (вес). Используя алгоритм Джикстры, мы можем определить, какой маршрут будет наилучшим для обоих людей, чтобы добраться до места назначения. Учитывая, что человек может перемещаться только в один узел за раз, и оба человека перемещаются одновременно, каков был бы хороший алгоритм для определения того, столкнутся ли они друг с другом при пересечении матрицы?

Когда вы выполняете два поиска Djikstra из двух начальных вершин, вы обновляете dist[] и prev[] массивы (глядя на псевдокод Вики)

Добавьте дополнительный массив 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 означает, что люди действительно встречаются в этом узле на шестом шаге.