Путь с кратчайшим временем восстановления

Проблема может быть описана следующим образом:

Произошел сбой сети узлов, и у каждого соединения (ребра) есть определенное время восстановления, пока оно не вернется в оперативный режим и два узла снова не соединятся. Наша цель состоит в том, чтобы найти путь между узлами с 1 по n, который запущен и работает раньше всех, и возвратить самое продолжительное время восстановления на этом пути.

Сеть можно представить в виде графа с неориентированными ребрами.

У нас есть три массива:

  1. Первый содержит исходные вершины
  2. Второй содержит вершины назначения
  3. Третий содержит время восстановления каждого соединения (края).

Пример:

{1,2,2,3}, {2,3,4,4}, {1,5,10,2}

где время восстановления соединения между узлами 1 и 2 равно 1 и т. д.

Оптимальный путь от 1 до n = 4 — это 1-2-3-4, так как максимальное время восстановления на этом пути равно 5, по сравнению с путем 1-2-4, где максимальное время восстановления равно 10.

Здесь важно отметить, что имеет значение только максимальное время восстановления на каждом пути, т. е. длина пути — это не сумма периодов ожидания, а длина самого длительного времени ожидания соединения. между двумя узлами для восстановления. Каждое время восстановления рассчитывается из t = 0, поэтому времена восстановления независимы, и порядок не имеет значения.

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

Я подошел к этой проблеме, используя алгоритмы Дейкстры и Беллмана-Форда, но не могу понять, как модифицировать алгоритмы для получения желаемого результата. Может быть не более 10^5 соединений.


graph algorithm shortest-path dijkstra bellman-ford
person Mikael Törnwall    schedule 31.03.2019    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Это легко сделать с помощью DSU (https://en.wikipedia.org/wiki/Disjoint-set_data_structure< /а>):

  1. Отсортировать все ребра по весу в порядке возрастания
  2. Цикл через ребра, если узлы u и v находятся в разных непересекающихся множествах, объединить их в один непересекающийся набор
  3. Если после слияния узлы 1 и N находятся в одном наборе, ответ является весом текущего ребра, и мы можем выйти из цикла.

Сложность: O (E log E + V log V)

person Photon    schedule 31.03.2019

arrow_upward
0
arrow_downward

DSU — самое красивое решение, как описывает Photon.

Другое возможное решение использует бинарный поиск + dfs/bfs/Dijkstra/Bellman-Ford/

Этот алгоритм будет запускать DFS/BFS не более чем в журнале (максимально возможная стоимость края).

Алгоритм будет работать следующим образом:

lo = 0, hi = largest cost from any edge from a graph
mid = dummy_value

while ( lo < hi ):
    mid = (lo + hi) / 2
    check if there is a path from source to destination using only edges with cost <= mid
    if there is a path:
        hi = mid
    else:
        lo = mid + 1

return mid

Решение, использующее DSU, имеет лучшую сложность во время выполнения, но это вводит идею выполнения бинарного поиска по ответу, что является классической идеей в решении проблем. В некоторых задачах выполнение DSU невозможно.

person Francisco Geiman    schedule 01.04.2019