кратчайший путь с поворотом одной кромки на ноль

задан неориентированный взвешенный граф G и две вершины: начальная вершина и конечная вершина

Какой самый эффективный алгоритм, который находит кратчайший путь от начала до конца с возможностью обратить вес ровно одного ребра в ноль?

РЕДАКТИРОВАТЬ: я знаю алгоритм Дейкстры, но, как я уже сказал, в этой проблеме ситуация иная: нам разрешено повернуть одно ребро в ноль,

Я хочу знать, как эффективно решить эту проблему, на самом деле, один из способов - итеративно обнулять веса ребер! и применять алгоритм Дейкстры на каждом шаге, но я ищу более эффективный способ

Благодарность


algorithm shortest-path
person user1711001    schedule 31.12.2012    source источник
comment
Вы спрашиваете, как найти кратчайший путь? Или как эффективно пересчитать кратчайший путь после удаления ребра? В любом случае, этот вопрос повторяется.   -  person BlueRaja - Danny Pflughoeft    schedule 31.12.2012
comment
нет, я знаю алгоритм Дейкстры, но, как я уже сказал, нам разрешено обнулить вес одного ребра (НЕ УДАЛЯТЬ КРАЙ!), я хочу знать, как можно эффективно решить эту проблему, используя Дейкстру или другой способ!   -  person user1711001    schedule 31.12.2012
comment
Djikstra должен без проблем обрабатывать вес ребер, равный 0.   -  person BlueRaja - Danny Pflughoeft    schedule 31.12.2012
comment
я знаю, но исходный граф не имеет ребра с нулевым весом, я должен определить, поворот какого ребра к нулю дает минимальный путь от начала до конца,   -  person user1711001    schedule 31.12.2012

Ответы (2)


arrow_upward
8
arrow_downward

Вы можете решить эту проблему, используя алгоритм Джикстры на расширенном графе в два раза больше.

Предположим, у вас есть вершины 1 ... n.

Определите новый граф так, чтобы для каждого ребра a-> b с весом w в оригинале определите ребра a-> b с весом w, a-> b + n с весом 0 и a + n-> b + n с вес w.

Идея состоит в том, что вершины n + 1..n + n являются дубликатами, содержащими копию исходного графа. Переход от оригинала к дубликату представляет собой использование вашей особой способности превращения ребра в 0. Обратите внимание, что, оказавшись в дубликате, нет возможности вернуться к исходному графу, поэтому эту особую способность можно использовать только один раз.

Поэтому вам просто нужно решить проблему на расширенном графе перехода от начала до конца + n, чтобы найти кратчайший путь, включая вашу возможность установить единичный вес на 0.

person Peter de Rivaz    schedule 31.12.2012

arrow_upward
-1
arrow_downward

алгоритм Дейкстры обычно используется для решения этих типов проблем. Кроме того, это немного похоже на проблему TSP, хотя я могу ошибаться в этой части.

person Woot4Moo    schedule 31.12.2012