Найдите кратчайший путь между двумя узлами в ориентированном взвешенном графе

У меня есть ориентированный взвешенный граф G = <V, E>. Мне нужно найти кратчайший путь между s и t в O((V + E)*logV). Это была бы очень простая задача, если бы у меня был классический метрический вес пути. Но это не так.

Weight of path = two heaviest edges in this path.

Поэтому классический Dijkstra's algorithm with modified binary heap не работает. Я думаю, что я должен изменить этот алгоритм. Я пытаюсь это сделать, но у меня нет успеха.

Example.

введите здесь описание изображения

Вес пути между 3 и 5 = 4 + 2 = 6

Вес пути между 3 и 7 = 4 + 4 = 8


graph algorithm computer-science shortest-path graph-algorithm
person Max    schedule 20.12.2014    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Отредактировал мой ответ на основе встречного примера Дэвида Эйзенстата.

Пример, который вы приводите в своем вопросе, не является хорошим примером того, когда Дейкстра не сработает.

Я считаю, что вы можете сделать это, изменив Dijkstra. Ключевым моментом является отслеживание нескольких альтернатив для каждой вершины. Вам нужно не только хранить веса, составляющие кратчайший путь, вы также должны хранить альтернативы, где макс ‹ кратчайший.макс и мин > кратчайший.мин.

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

person wvdz    schedule 20.12.2014
comment
Как упорядочить пары весов в очереди приоритетов? - person David Eisenstat; 20.12.2014
comment
Могу я уточнить? Правильно ли я понимаю, что вы хотите хранить два самых тяжелых ребра в каждой вершине? Я тоже хотел так сделать. Однако есть и обратный пример. - person Max; 20.12.2014
comment
@Max: Тогда, пожалуйста, приведите контрпример. Дэвид: Я не вижу проблемы. Вы заказываете их на общий вес. - person wvdz; 20.12.2014
comment
@popovitsj, я знаю, что есть и обратный пример. Мой профессор так сказал несколько дней назад. Но у меня его нет. - person Max; 20.12.2014
comment
Проблема в отсутствии оптимальной подструктуры. Предположим, что у нас есть граф a-›b (4), b-›d (4), a-›c (2), c-›d (5), d-›e (???) и мы хотим добраться от а до е. Если d-›e имеет вес 4, то нам нужны a-›b-›d-›e (8 ‹ 9). Если d-›e имеет вес 1, то нам нужны a-›c-›d-›e (7 ‹ 8). - person David Eisenstat; 20.12.2014
comment
@popovitsj, спасибо за помощь. Надеюсь, это правильный алгоритм. контрпримера не придумал :) - person Max; 21.12.2014