Мой алгоритм:
построить новый граф G', тогда как для каждой вершины v в V создать две вершины v_0 и v_1 в G', и для каждого ребра (u, v) в E, создайте два ребра (u_0, v_1) и (u_1,v_0) в G'. Запустите Dijkstra на G', начиная с s_0.
Все пути в G', заканчивающиеся на v_0, имеют четное число ребер, поэтому кратчайший путь четной длины к вершине t в G можно найти, определив кратчайший путь от s_0 до t_0 в G'.
Как я могу доказать правильность этого алгоритма?
Все пути в G', заканчивающиеся на
v_0, имеют четное число ребер.
Это не совсем так. v_0 имеет некоторое входящее ребро, скажем, p_1 -> v_0, и этот путь имеет нечетное количество ребер (1).
Но ты близок к истине, однако. Если мы возьмем исходный граф G и для каждой вершины v создадим две вершины v_0 и v_1 в G', то мы сможем разбить G' на два (непересекающихся) набора вершин - 0-вершин и 1-вершин.
И я заявляю, что:
Все пути в
G', которые начинаются из любой0-вершины и заканчиваются в любой0-вершине, имеют четное число ребер.
Это верно, потому что G' является двудольным. По определению двудольный граф — это граф, вершины которого можно разделить на два непересекающихся множества (в нашем случае 0-вершин и 1-вершин) так, что каждое ребро соединяет две вершины из разных множеств. То, как мы построили G', делает его двудольным, потому что мы никогда не соединяем вершины, принадлежащие одному и тому же множеству (мы всегда соединяем u_0 с v_1 и наоборот).
В двудольном графе, таком как G', каждый путь, начинающийся с вершины одного из наборов и заканчивающийся вершиной того же набора, имеет четное число ребер. Осталось только найти кратчайший (с выбранным вами алгоритмом кратчайшего пути).
Предполагая, что начальный узел - S, а конечный узел - F
На модифицированном графе, если мы перемещаемся из ui в vj через ребро, соединяющее два узла, то j=(i+1) mod 2 определяется способом определения ребер.
Итак, если мы путешествуем из ui в vj по любому произвольному пути, j=(i+n) mod 2, где n — длина пути. (вывод 1)
Итак, если мы путешествуем из S0 в F0 по некоторому пути, 0 = (0 + n) mod 2 означает, что n четно
Таким образом, это доказывает, что любой путь из S0 в F0 проходит по четным ребрам (вывод 2)
Кроме того, основываясь на том, как ребра определены в новом графе, мы можем сказать, что для любого ребра (u,v) в старом графе ребро (ui,vj ) существует в новом графе для некоторых i,j (вывод 3)
Теперь, если в исходном графе существует путь четной длины, пусть кратчайший путь будет SA1A2...A2m-1F, где Ai может повторяться. (Четные ребра подразумевают нечетное количество узлов). Затем на новом графе мы можем начать с S0 и пройти через S0A1iA2j...A2m-1kFm, чтобы приземлиться на F ( из вывода 3). Тогда индекс на F будет (0 + 2m-1 +1) mod 2 = 0 (из вывода 2). Следовательно, на новом графе тоже будет путь такой же длины.
Следовательно, если решение существует, то и в новом графе существует путь из S0 в F0 (вывод 4)
Кроме того, в зависимости от того, как ребра определены в новом графе, для каждого ребра от ui до vj в исходном графе есть ребро от u до v. . Следовательно, для любого пути в новом графе от ui до vj существует соответствующий путь от u до v в старом графе такой же длины
Следовательно, если путь из S0 в F0 существует, то в исходном графе существует соответствующий путь такой же длины (вывод 5)
Выводы 2,4 и 5 вместе доказывают, что кратчайший путь из S0 в F0 является правильным ответом. Если путь не найден, то его нет и в исходном графе (из вывода 4)
Значит алгоритм правильный
(u_0 , v_1)и(u_1,v_0), не будет ли новый граф просто двумя несвязанными графами, которые оба эквивалентны исходному графу? - person Abhay Aravinda schedule 20.10.2020