Кратчайший путь, 2 весовые функции

Вопрос звучит так: Дан ориентированный граф G = (V,E), две вершины s,t и две весовые функции w1, w2. В G нет циклов с отрицательным весом (как по w1, так и по w2). Мне нужно описать алгоритм, который находит кратчайший путь из s в t по w2 среди заданных кратчайших путейs из s в t.

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

Я понятия не имею, как это решить (даже хромой). любая помощь будет оценена.


algorithm shortest-path bellman-ford
person user2375340    schedule 11.04.2014    source источник
comment
можно было просто использовать BFS   -  person Sam G-H    schedule 11.04.2014
comment
@SamG-H, можешь быть более конкретным? Мне нужно, чтобы путь был кратчайшим как для w1, так и для w2, поэтому я не понимаю, как это сделать без использования Bellman-Ford.   -  person user2375340    schedule 11.04.2014
comment
Не могли бы вы объяснить свой вопрос более четко, пожалуйста. Я не думаю, что понимаю. :/   -  person Sukrit Kalra    schedule 11.04.2014
comment
@SukritKalra Вопрос уже дает мне кратчайшие пути от s до t по весовой функции w1. среди этих путей мне нужно найти кратчайший путь из s в t с помощью весовой функции w2. значение: мне нужно найти кратчайший путь от s до t как по w1, так и по w2. по-видимому, я думаю, что уже заданные кратчайшие пути по w1 должны упростить алгоритм.   -  person user2375340    schedule 11.04.2014
comment
Предполагая, что существует x количество путей со стоимостью X (которая является минимальной среди всех возможных путей), вы можете просто применить весовую функцию w2 к каждому из x путей и вычислить минимум. Так, например, путь из s -> t = s -> d -> t, затем вычислить вес с помощью w2(s, d) + w2(d, t). Сделайте это для всех x путей и получите минимум.   -  person Sukrit Kalra    schedule 11.04.2014

Ответы (1)


arrow_upward
1
arrow_downward

Идея состоит в том, чтобы сделать w2 важным, но не настолько, чтобы повлиять на исход w1.

Пусть SUM2 будет суммой w2 по всем ребрам: SUM2 = Sum { w2(e) | e in E } и min{w1} = min { w1(e) | e in E } (минимальное значение согласно w1)

На основе этого создайте новую весовую функцию:

w(e) = w1(e) + w2(e)/min{w1}*(SUM2+1)

Теперь, учитывая все кратчайшие пути в соответствии с w1, очевидно, почему среди них предпочтение будет отдаваться кратчайшим путям в соответствии с w2.

С другой стороны, w2 недостаточно «сильна», чтобы преодолеть важность w1 и доминировать, поскольку обратите внимание, что общая сумма ВСЕХ ребер в соответствии с w2 теперь меньше, чем один узел в w1

Используйте приведенный выше w с любым алгоритмом кратчайшего пути, чтобы получить желаемый кратчайший путь.

person amit    schedule 11.04.2014