Модифицированный алгоритм Дейкстры

Нам дан ориентированный граф с весами ребер W, лежащими между 0 и 1. Стоимость пути от исходного узла к целевому — это произведение весов ребер, лежащих на пути от исходного узла к целевому. Я хотел узнать об алгоритме, который может найти путь с минимальной стоимостью за полиномиальное время или с использованием любой другой эвристики.

Я думал о том, чтобы взять логарифмические значения весов ребер (взяв значения мода), а затем применить dijkstra для этого графика, но думаю, что возникнут проблемы с точностью, которые невозможно рассчитать.

Есть ли другой лучший способ или я могу улучшить подход журнала.


graph algorithm shortest-path dijkstra heuristics
person sagar verma    schedule 07.11.2016    source источник
comment
Наоборот, сумма логов, вероятно, будет более стабильной, чем последовательные продукты.   -  person Ami Tavory    schedule 07.11.2016
comment
Метод Дейкстры не работает для отрицательных длин ребер. Попробуйте использовать алгоритм Беллмана Форда, если вам подходит сложность O(|V|.|E|).   -  person Abhishek Bansal    schedule 07.11.2016

Ответы (1)


arrow_upward
1
arrow_downward

В алгоритме Дейкстры, когда вы посещаете узел, вы знаете, что более короткой дороги к этому узлу нет. Это неверно, если вы умножаете ребра с весами от 0 до 1, так как если вы посещаете больше вершин, вы получите меньшее число.

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

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

  1. Найдите топологический порядок DAG.
  2. Для каждой вершины вам нужно сохранить стоимость пути. Инициализируйте это до единицы в начале.
  3. Пройдите через DAG в топологическом порядке, начиная с начальной вершины. В каждой вершине проверьте всех дочерних элементов и, если стоимость меньше предыдущей, обновите ее. Сохраните также вершину, в которой вы достигли этой вершины с наименьшей стоимостью.

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

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

person Ari Hietanen    schedule 07.11.2016