Поиск края, который уменьшает кратчайший путь от A до B самым

Question

Учитывая неориентированный граф G с весами ребер, набор ребер-кандидатов (длина | V | + | E |) и вершины A и B, найдите край, который максимально уменьшает кратчайший путь от A до B.

Например:

Грани-кандидаты пунктирные линии. Самый короткий путь от A до B - A -> C -> D -> G -> B (стоимость 7). Но с ребром (D, B) кратчайший путь A -> C -> D -> B (стоимость 6), поэтому алгоритм должен возвратиться (D, B).

я придумал скотину силового решения O ((| V | + | E |)^2 журнала | V |):

• для каждого кандидата края:
  • добавить край к графе
  • запустить Дейкстры, чтобы найти стоимость кратчайшего пути от А до в
  • удалить пограничную
• RETU rn к краю кандидата, который приводит к кратчайшему пути

но есть ли что-нибудь лучше?

Answer 1

Один из подходов заключается:

• Выполнить Дейкстра из А и хранить расстояние до каждого узла п в [N]
• Run Дейкстрой из B и хранить расстояние до каждого узла п в В [п]
• Петля над каждым краем кандидата. Для края с весом w, соединяющего вершины x и y, сравните w + A [x] + B [y] и w + A [y] + B [x]

Меньше w + A [ x] + B [y] и w + A [y] + B [x] дает кратчайший путь между A и B, когда используется край кандидата.