Обобщенный алгоритм Дейкстры

[NightBlade74]

Докозательство

Проверочное слово "коза".

[wataru]

Спасибо!

[MasterMentor]

+/+/+/+

[igand]

Кстати, если "не уменьшается" заменить на "не увеличивается", а "кратчайший" заменить на "длиннейший", то можно искать не кратчайший, а длиннейший путь.

Пример такой задачи: на рёбрах записаны числа от 0 до 1 - вероятности успешной передачи сигнала по этому ребру. Требуется найти путь с максимальной вероятностью успешной передачи, то есть с максимальным произведением весов рёбер на пути.

Поскольку все рёбра от 0 до 1, то при добавлении ребра к пути произведение не увеличивается. Остальные свойства также выполняются. Поэтому вполне себе решается Дейкстрой, но для max, а не min.

[wataru]

Можно свести к обычной функции, если считать минус логарифм произведения всех ребер. Тогда даже знаки менять не надо. Иди минус произведение всех ребер.

[igand]

Да, здесь с минус логарифмами сводится к обычной Дейкстре (но надо ещё догадаться).

Вот ещё такой пример задачи. На рёбрах графа написаны пропускные способности. Требуется найти путь из точки A в точку B с максимальной пропускной способностью. Она, понятно, определяется самым "узким" местом, то есть ребром минимального веса на пути. Тоже вполне себе решается Дейкстрой.

[wataru]

Это я к тому, что не надо вводить еще случай с обратными знаками и максимизацией. Можно воткнуть минус в функцию расстояния и все укладывается в описанный случай. Так, в вашей задаче можно взять за функцию минус минимум в пути.

[Melirius]

Произведение обратных ещё.

[malkovsky]

Вообще кажется, что по сути уникальными являются пункты 1 и 4 (из корректных), 2 -- это применение обычного Дейкстры на модифицированных весах с сохранением оптимальных путей, 3 сводится к обычному сетапу логарифмированием, а веса на вершинах можно перенести на рёбра небольшим преобразованием графа. К слову пункт 2 (из некорректных) вроде как решается Дейкстрой после разделения вершин. В любом случае хорошее обобщение.

У меня большое подозрение, что это все это очень похоже на кратчашие пути на полукольцах. Там есть например такая неочевидная функция: длина пути -- это конкатенация символов вдоль пути, а минимальная длина между s->t -- это longest common prefix всех s->t путей. Нахождение таких "кратчайших путей" например позволяет построить по конечному автомату эквивалентный ему, в котором символы появляются как можно раньше. Как сейчас не знаю, но раньше в распознавании речи это позволяло уменьшить задержку в онлайн сценарии.

[wataru]

Функция с общим префиксом интересная, но тут что-то еще более общее, ибо это не функция от одного пути, а функция от всего графа целиком - от всех возможных путей.

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