Нахождение кратчайшего пути между любыми двумя узлами, принадлежащими двум непересекающимся подмножествам графа - PullRequest
5 голосов
/ 14 марта 2012

Существует неориентированный график, в котором каждому узлу присваивается какой-то цвет.Я должен найти кратчайший путь от любого синего узла к любому красному узлу.(Другие цвета могут также существовать на графике, и, хотя это не имеет значения, но неизвестно, сколько цветов существует.) Как я могу сделать это за полиномиальное время?

1 Ответ

7 голосов
/ 14 марта 2012

В качестве подсказки добавьте два новых узла в граф - назовите их s и t. Соедините s с каждым синим узлом с ребром стоимости 0, а каждый красный узел - с ребром стоимости 0. Затем найдите кратчайший путь от s до t.

Надеюсь, это поможет!

...