Кратчайшее расстояние между заданными узлами в двунаправленном взвешенном графе путем удаления любых K ребер.

Опубликовано: 21 Сентября, 2022

Для данного положительного целого числа K и взвешенного неориентированного связного графа из N узлов и E ребер в виде массива Edges[] типа {u, v, W}, представляющего ребра между Node u и Node v с весом W , задача состоит в том, чтобы найти кратчайшее расстояние между двумя заданными узлами S и D после уменьшения стоимости не более чем K ребер до 0 .

Примеры:

Input: N = 5, K = 1, Edges[][] = {{0, 1, 1}, {0, 4, 1}, {1, 2, 2}, {2, 3, 4},  {4, 3, 7}}, s = 0, d = 3
Output: 1
Explanation:
Below is the graph for the given test case:

There are 2 possible routes between 0 and 3 viz. {0->1->2->3} and {0->4->3}
after reducing the distance of edge 4->3 to zero, the second route becomes 0->(4, 3) and hence the minimum distance is 1.

Input: N = 5, K = 2, Edges[][] = {{0, 1, 2}, {0, 2, 3}, {2, 1, 2}, {2, 3, 1}, {3, 1, 2}, {3, 4, 3}, {4, 2, 4}}, s = 0, d = 3
Ouput: 2

Подход: данная проблема может быть решена с помощью DFS Traversal и сохранения всех возможных путей между двумя заданными узлами. Выполните следующие шаги, чтобы решить данную проблему:

  • Инициализируйте переменную, скажем, minimumCost как INT_MAX, которая хранит результирующее кратчайшее расстояние.
  • Пройдите все пути от узла S к узлу D в графе, используя DFS Traversal, и сохраните все веса ребер от узла S до D, полученные в векторе векторов, скажем, edgePath[] .
  • После вышеуказанных шагов отсортируйте каждый вектор, хранящийся в EdgePath[], в порядке убывания.
  • Пройдите вектор векторов edgePath[] для каждого вектора, скажем, A[] , выполните следующие шаги:
    • Найдите сумму первых K самых больших ребер в A[] .
    • Обновите значение minimiumCost до минимума из текущих (totalSum — сумма) и mininmumCost .
  • После выполнения вышеуказанных шагов выведите в качестве результата значение MinimumCost .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O((N*log N)N N )
Вспомогательное пространство: O(N 2 )

Эффективный подход. Описанный выше подход также можно оптимизировать на этапе, когда сортировка выполняется после нахождения всех возможных путей. Вместо сортировки идея состоит в том, чтобы использовать MinHeap для вычисления суммы K наибольших весов в графе, чтобы уменьшить временную сложность до O (N * log K) для этих шагов.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O((N*log K)N N )
Вспомогательное пространство: O(N 2 )

РЕКОМЕНДУЕМЫЕ СТАТЬИ