#algorithm #dijkstra #shortest-path #np-complete #floyd-warshall
#алгоритм #dijkstra #кратчайший путь #np-завершено #флойд-Варшалл
Вопрос:
Представьте, что вам дан взвешенный неориентированный полный граф с n узлами с неотрицательными весами Cij, где для i = j Cii = 0, а для i ! = j Cij > 0. Предположим, вам нужно найти максимально короткий путь между любыми двумя узлами i и j . Здесь вы можете легко использовать Floyd-Warshall или использовать Dijkstra n раз, или что угодно, а затем просто найти максимум среди всех n ^ 2 кратчайших путей.
Теперь предположим, что Cij не являются постоянными, а скорее могут принимать два значения, Aij и Bij, где 0 <= Aij <= Bij. У нас также есть Aii = Bii = 0. Предположим, вам также нужно найти максимально короткий путь, но с ограничением, что m ребер должны принимать значение Bij и другие Aij. И, если m > n ^2, то все ребра равны Bij. Но, при нахождении кратчайшего пути i -> p1 -> … -> pk -> j, вы заинтересованы в наихудшем случае, в том смысле, что на этом пути вам нужно выбрать те ребра, которые принимают значение Bij, так что значение пути будет максимальным, если у вас есть фиксированные узлы в его направлении.
Например, если у вас есть путь длиной четыре i-k-l-j, и в оптимальном решении на этом пути только один вес изменяется на Bij, а другие принимают значение Aij. И пусть m1 = Bik Akl Alj, m2 = Aik Bkl Alj, m3 = Aik Akl Blj, значение этого пути равно max{m1, m2, m3}. Итак, среди всех путей между i и j вы должны выбрать такой, чтобы максимальное значение (описанное как в этом примере) было минимальным (что является вариантом определения кратчайшего пути). И вы должны сделать это для всех пар i и j.
Вам не дается ограничение на то, сколько вам нужно изменить на каждом пути, а скорее значение m, количество весов, которые следует изменять во всем графике. И проблема состоит в том, чтобы найти максимальное значение кратчайшего пути, как описано.
Кроме того, мой вопрос таков: является ли эта NP-сложная задача, или существует какое-то полиномиальное решение?
Комментарии:
1. Должен ли путь содержать каждую вершину не более одного раза или разрешено посещать вершину дважды или больше раз?
2. Не более одного раза. Однако, если вы найдете кратчайший путь, который содержит некоторую вершину более одного раза, я думаю, что невозможно быть кратчайшим, поскольку ребра неотрицательны.
3. Разрешено ли изменять m B-ребер при каждом выборе (начальная вершина, конечная вершина) или нет? Если да, то эквивалентен ли ваш вопрос следующему? Найдите пару вершин {u, v}, максимизирующую f (u, v), где f (u, v) — минимальное значение g (P) по всем путям P от u до v, а g (P) — максимальная длина пути, достижимая путем задания минимальных (m, nEdges (P)) ребер в P на их B-длины, а остальные — на их A-длины.
4. Если предполагается, что m B-ребер не должны меняться, то эквивалентно ли это: Найдите пару вершин {u, v}, максимизирующую h (u, v), где h (u, v) — максимальное значение a (u, v, G’) по всем графам G’, имеющим те же ребра, что и входной граф G, и при этом ровно m из этих ребер присвоены их B-длины, а остальным присвоены их A-длины, а a (u, v, G ‘) — минимальная длина пути от u до v в G’?