Диаграмма кратчайшего пути Dijkstra не будет работать

У меня есть график с положительными весами и положительными весами узлов. Длина пути определяется как сумма всех весов ребер вдоль пути плюс максимальный вес узла, встречающийся вдоль пути.Диаграмма кратчайшего пути Dijkstra не будет работать

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

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

Посмотрите на график, где Dijkstra не работает: http://i.imgur.com/FQhRzXV.jpg Цифры в зеленых являются ярлыками узлов. Все в синем - это вес (вес узлов и ребер). Допустим, я хочу вычислить кратчайший путь между узлами 1 и 7 (помечен зеленым цветом). Проблема с Dijkstra заключается в том, что узел 4 всегда записывает путь 1-8-9-4, поскольку его длина меньше пути 1-2-3-4 (прежняя длина 9 против последней длины 13). Но для достижения узла 7 путь 1-8-9-4-5-6-7 длиннее 1-2-3-4-5-6-7.

источник

2013-09-21 elexhobby

Что вы пытались и почему это не получилось? Я уверен, что модифицированный Dijkstra будет работать :-) –

Исправить начальный узел. Для каждого из своих соседей сохраните пару чисел - (самый короткий путь к этому соседу, максимальный вес узла, встречающийся до сих пор на пути к этому узлу). Поместите их в очередь и выберите узел с самым коротким путем. Продолжать. При добавлении нового узла b, подключенного к посещенному узлу a, если вес b <максимальный вес узла встречается на пути к узлу a, пара на b является (кратчайший путь к весу + края ab, максимальный узел, встречающийся до a). Else, пара на b (кратчайший путь к узлу a-max до + веса узла b + вес края ab, вес узла b). – elexhobby

Я думаю, что вы решили «путь с минимальным общим весом», а также отслеживайте самый большой взвешенный край на этом пути ». Я думаю, что проблема, вероятно, связана с «путём с минимальным (общий вес плюс наибольший вес)». Простое отслеживание самого большого веса не решит этого. – DanielV

Если вы можете простить один порядок больше полиномиальное время, то довольно легко алгоритм:

ModifiedShortestPath(u, v, G) { 
    X = StandardardShorestPath(u, v, G); 
    E = heaviest edge in X 
    F = all edges in G of weight >= E 
    Y = ModifiedShortestPath(u, v, G - F); // recur here on G without the F edges 
    return Min(X, Y); 
}

Среда выполнения этого является | E | раз больше, чем ваш стандартный короткий путь.

источник

2013-09-21 20:08:57 DanielV

Диаграмма кратчайшего пути Dijkstra не будет работать

ответ

Смежные вопросы