кратчайший путь в графе с цветными краями

Question

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

Я пытался использовать BFS, но не смог найти решение.
есть идеи, как начать?

Answer 1

Во-первых, я предполагаю, что количество цветов является фиксированным.Затем я бы предложил алгоритм Dijkstra для установки меток (сравните с Pareto Dijkstra), в результате чего время выполнения O (n log (n) + m):

Используйте обобщенный Dijkstra, чтобы найти кратчайший путь: каждыйузел имеет список меток, одна метка состоит из длины от начального узла и всех посещенных цветов.Одна метка доминирует над другой меткой в ​​этом узле, если (1) она имеет меньшую длину и (2) она включает в себя все цвета другой метки.Доминирующий ярлык удаляется напрямую.Подобно dijkstra, у вас есть приоритетная очередь, из которой вы всегда расслабляете узел с меньшей длиной.Перетаскивание ребра в узел v увеличит длину метки на длину конца и добавит цвет кромки к метке.Метка добавляется в список меток узла v. При назначении целевого узла меткой, содержащей все три цвета, вы нашли кратчайший путь.Обратите внимание, что вы должны сохранить узел-предшественник для каждой метки, если вы хотите восстановить кратчайший путь в конце.

Вы начинаете с начальной метки на начальном узле с (0, {}) (нулевая длина ибез цвета).

Каждый узел может быть установлен не более одного раза для каждой комбинации набора цветов, поскольку в этом случае существует только 8 (фиксированных) таких комбинаций, время выполнения равно алгоритму Дейкстры, который равен O (n* log (n) + m) для лучшей реализации.

Answer 2

Я бы использовал BFS, и, начиная с каждого узла, я рассчитывал первый действительный путь, который можно обнаружить с этого узла, сохранял это значение и переходил к следующему.

График может быть представлен в виде матрицы с цветом каждого ребра (скажем, -1 (без ребра), 0,1,2) в качестве значения ребра в матрице.

Пути, когда вы их обнаруживаете, могут быть помещены в пару массивов, один из которых удерживает шаги на пути, а другой проверяет три цвета.

Answer 3

Существует тривиальное решение следующим образом.

Создайте нормальную дижстру на графике, предполагая, что цвета нет.

Угадайте 3 ребра по одному на каждый цвет.Для всех m ^ 3 возможных предположений пусть ребра будут r1 --- r2, b1 --- b2, g1 --- g2, мы получим 24 возможных пути их попадания на путь (8 способов, как вы можете ориентировать ребра, 6 для перестановки).

Так как у вас уже есть нормальные данные dijkstra, как только вы закончите с этим, вы получите в постоянное время результат, минимизируйте все догадки.

Повторите это для всех n вершин.

Я согласен, что окончательная сложность O (nm ^ 3) обычно слишком велика, но иногда тривиальный алгоритм работает.

Answer 4

для создания нового графика (6 раз) состоит из трех копий исходного, первый включает только ребра одного из цветов, второй включает также ребра другого цвета и соединяет их с ребрами извторой цвет и третья копия будут иметь все ребра и связаны со вторым графом ребрами из третьего цвета.затем запустите dijkstra, чтобы найти кратчайший путь от s1 до t3.поскольку мы не знаем, какой будет порядок, мы сделаем то же самое для всех 6 возможных порядков цветов, а затем выберем самый короткий из 6 кратчайших путей, которые мы получим.