Найдите путь от вершины s к вершине t с минимальным количеством цветовых альтернатив - PullRequest
Новая
       110

Найдите путь от вершины s к вершине t с минимальным количеством цветовых альтернатив

1 голос
/ 12 июля 2020

Пусть $G=(V,E)$ be a directed graph, and let $c:E\mapsto {red,blue}$ be an edge-coloring in red and blue. Let s,t be vertices in G. Find a path from s to t (if exists) so that the number of color changes along this path is minimal.

I have tried to do as follows:

  1. Let $G_r$ be the graph obtained by removing all the blue-colored edges of G. Let $G_b$ be the graph obtained by removing all the red-colored of G.
  2. Let $G_{r}^{SCC}$ be the сильно связан график $G_r$, computed using этого алгоритма.
  3. Пусть $G_{b}^{SCC}$ be the сильно связный график $G_b$, computed using этот алгоритм.
  4. Раскрасьте вершины $G_{r}^{SCC}$ in red, and color the vertices of $G_{b}^{SCC}$ in blue.
  5. Let $G'=(V',E')$ be the graph obtained by merging $G_{r}^{SCC}$ with $G_{b}^{SCC}$.
  6. Define the weight of each (existing) edge in G' as 0.
  7. For each $(u,v)\in E$ such that u belongs to the strongly connected component $C_u$ and v belongs to the strongly connected component $C_v$ do as follows:
  • if $C_u \neq C_v$ and $color(C_u)\neq color(C_v)$ add edge $(C_u ,C_v)$ to G' and define its weight as 1.
  1. Используйте алгоритм Дейкстры, чтобы найти кратчайший путь от синего компонента сильной связности s к синей и красной компонентам сильной связности t .
  2. Используйте алгоритм Дейкстры, чтобы найти кратчайший путь от красной сильно связной компоненты s к синей и красной сильно связным компонентам t.
  3. Пусть p обозначает кратчайший путь среди четыре мы только что нашли. (а именно, p имеет минимальное количество альтернативных цветов). p - серия компонент сильной связности. Разверните каждый из них с помощью DFS, чтобы найти соответствующий путь в G.

Этот алгоритм может работать за O (E + V * log (v)). Можно ли его улучшить или упростить?

1 Ответ

1 голос
/ 15 июля 2020

Я не совсем понимаю ваш алгоритм, в частности, на этапе 4 вы раскрасите каждую вершину двумя краями разного цвета в два цвета - синий и красный ... Поэтому я не буду пытаться улучшать ваш алгоритм, но представлю один из моих - вариант BFS со временем O (E + V).

Идея: итерация по краям графа и измерение глубины как количество раз, которое вы меняли цвета.

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

  1. Запускайте BFS только на красных краях, начиная с s (который является первым элементом в очереди BFS), если вы просматривали вершину на синем краю, сохраните ее в другой очереди.
  2. Отметьте все узлы, которые вы видели, номером i (в начале i=0).
  3. Возьмите очередь для синих краев и сделайте ее своей основной.
  4. Выполните этапы с 1 по 3, но поменяйте цвета и добавьте 1 к i.

В конце число в t - это минимальное количество замен, выполненных для достижения t .

...