Найдите максимальное кратчайшее расстояние в каждом компоненте графика

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

Для данного матричного графа смежности [][] взвешенного графа, состоящего из N узлов и положительных весов, задача для каждой связной компоненты графа состоит в том, чтобы найти максимальное среди всех возможных кратчайших расстояний между каждой парой узлов.

Примеры:

Input:

Output:

8 0 11 

Explanation: There are three components in the graph namely a, b, c. In component (a) the shortest paths are following:

  1. The shortest distance between 3 and 4 is 5 units.
  2. The shortest distance between 3 and 1 is 1+5=6 units.
  3. The shortest distance between 3 and 5 is 5+3=8 units.
  4. The shortest distance between 1 and 4 is 1 unit.
  5. The shortest distance between 1 and 5 is 1+3=4 units.
  6. The shortest distance between 4 and 5 is 3 units.

Out of these shortest distances:
The maximum shortest distance in component (a) is 8 units between node 3 and node 5.
Similarly, 
The maximum shortest distance in component (b) is 0 units.
The maximum shortest distance in component (c) is 11 units between nodes 2 and 6.

Input:

Output:

7 

Explanation: Since, there is only one component with 2 nodes having an edge between them of distance 7. Therefore, the answer will be 7.

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

  • Определите функцию maxInThisComponent(vector<int> component, vector<vector<int>> graph) и выполните следующие шаги:
    • Инициализируйте переменную maxDistance как INT_MIN и n как размер компонента.
    • Перебрать диапазон [0, n), используя переменную i , и выполнить следующие задачи:
      • Переберите диапазон [i+1, n), используя переменную j , и обновите значение maxDistance как максимальное значение maxDistance или graph[component[i]][component[j]] .
    • Верните значение maxDistance в качестве ответа.
  • Инициализируйте посещаемый вектор размера N и инициализируйте значения как false .
  • Инициализируйте векторы, скажем, component[][] и temp[] для хранения каждого компонента графика.
  • Используя поиск в глубину (DFS) , найдите все компоненты и сохраните их в векторных компонентах[][] .
  • Теперь вызовите функцию floydWarshall(graph, V), чтобы реализовать алгоритм Флойда Уоршалла для нахождения кратчайшего расстояния между всеми парами компонента графа.
  • Инициализируйте вектор result[] для сохранения результата.
  • Инициализируйте переменную numOfComp как размер компонентов вектора[][].
  • Перебираем диапазон [0, numOfComp) с помощью переменной i и вызываем функцию maxInThisComponent(components[i],graph) и сохраняем возвращаемое ею значение в векторе result[] .
  • После выполнения вышеуказанных шагов выведите значения вектора result[] в качестве ответа.

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

Временная сложность: O(N 3 ), где N — количество вершин в графе.
Вспомогательное пространство: O(N)

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