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

Question

Нижеследующее изображение представляет собой представление вопроса, которое было задано мне во время интервью samsung. Мне пришлось написать программу, чтобы найти минимальное расстояние между I и M. Было дополнительное ограничение, что мы можем изменить один из ребер. Например, край FM может быть перемещен для присоединения кромки L и M, а значение края будет по-прежнему равно 4.

Если вы заметили, расстояние между I и M через I-> E -> F -> G - > M равно 20. Однако, если мы изменим один из ребер, так что теперь значение L to M edge равно 4. Нам нужно переместить край FM, чтобы теперь присоединиться к L и M. По этому методу расстояние между I и M равно 20.

Произвольный край u, v можно изменить на u, t или t, v. Его нельзя изменить на x, y. Поэтому одна из вершин в ребре должна быть одинаковой.

Пожалуйста, найдите изображение ниже, чтобы проиллюстрировать сценарий -

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

Answer 1

1. Если мы перемещаем край (A, B), новый конец должен быть либо начало S или целевой T вершина (в противном случае, ответ не является оптимальным).

2. Давайте предположим, что мы перемещаем край (A, B) и новый конец T (случай, когда он S обрабатывается аналогично). Нам нужно знать кратчайший путь от S до A, который не использует этот край (как только мы это узнаем, мы можем обновить ответ с помощью пути S->A->T).

3. Давайте вычислим кратчайший путь от S ко всем остальным вершинам, используя алгоритм Дейкстры.

4. Зафиксируем вершину A и вычислить два минимумов dist[B] + weight(A, B) для всех B прилегающих к A. Давайте перебираем все грани, смежные с A. Пусть текущий край равен (A, B). Если dist[B] + weight(A, B) равен первому минимуму, то пусть d будет вторым минимумом. В противном случае, пусть d будет первым минимумом. Мы должны обновить ответ d + weight(A, B) (это значит, что (A, B) теперь становится (A, T)).

Это решение линейно по размеру графика (не считая времени выполнения алгоритма Дейкстры).

Чтобы избежать дублирования кода, мы можем рассмотреть случай, когда край перенаправляется S путем замены S и T и работает один и тот же алгоритм (окончательный ответ является минимальным из результатов этих двух серий).

Answer 2

На графике, который вы указали, самый короткий путь, который я вижу, - I -> E -> F -> M с длиной 13.

Перемещение края F -> M так, что он соединяет L -> M только делает вещи хуже. Новый кратчайший путь I -> E-> F -> L -> M длиной 18

очевидный ответ, чтобы переместить край F -> M так, что он соединяет I непосредственно M, давая длину 4.

Иными словами, найдите самый короткий край, который подключен к I или M и используйте его для подключения I непосредственно к M.

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