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

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

0 голосов
/ 31 марта 2019

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

Произошел сбой в сети узлов, и каждое соединение (ребро) имеет определенное время восстановления, пока не вернется в оперативный режим, и оба узла не будут снова подключены. Наша цель - найти путь между узлами с 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 соединений.

Ответы [ 2 ]

0 голосов
/ 01 апреля 2019

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 невозможно.

0 голосов
/ 31 марта 2019

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

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

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

...