Дейкстра-добавление новой вертикали

Question

Я писал код для решения проблемы пути к ближайшему магазину в городе (у меня есть карта n вершин, некоторые дома, а некоторые магазины, и мне нужно найти кратчайший путь от каждого дома до магазина)Идея состоит в том, чтобы добавить новую вершину и подключить ее к каждому магазину с ребром веса 0, затем с помощью Dijkstra получить путь от каждого дома до этой вершины, но, как я думал, я придумал другую идею - что, если вместо добавления новой вершины я простопоставить 0 в массиве расстояний в индексах с магазинами и потом использовать дейкстры?Будет ли в моем массиве расстояний кратчайший путь до магазинов из каждого дома?

Answer 1

Фактически, идея, которую вы ищете, называется SPDP ( S hortest P air D isjoint P ATH). Как правило, найти общее решение невозможно, если исходящий алгоритм, вероятно, не , являющийся Жадным (т. Е. не гарантирует получение ответа, даже если существует существует один). Различные много парадигм могут быть развернуты для использования. Например, удалите ссылки каждого пути, который вы нашли в сети (например, установите их стоимость достаточно большим) и снова запустите алгоритм Дейкстры. Повторите этот шаг, пока вы получили все пути, которые вы хотите. Другая методология исходит из подхода Бхандари (или аналогично подходу Суурбалле). В этом подходе (который используется для получения двух непересекающихся путей), ссылки первого полученного пути меняются местами по направлению и стоимости (т. Е. Знак стоимости меняется между + и -), хотя этот подход требует алгоритма Беллмана-Форда.