Разница между кратчайшим и вторым кратчайшим путем в невзвешенном двунаправленном графе

Дан невзвешенный двунаправленный граф, содержащий N узлов и M ребер, представленный массивом arr[][2] . Задача состоит в том, чтобы найти разницу в длине кратчайшего и второго кратчайшего пути из узла 1 в N. Если второго кратчайшего пути не существует, выведите 0 .

Note: The graph is connected, does not contain multiple edges and self loops. (2<=N<=20)

Примеры:

Input: N = 4, M = 4, arr[M][2]={{1, 2}, {2, 3}, {3, 4}, {1, 4}}
Output: 2
Explanation: The shortest path is 1->4 and the second shortest path is 1->2->3->4. Hence, the difference is 2.

Input: N = 6, M = 8, arr[M][2]={{1, 2}, {1, 3}, {2, 6}, {2, 3}, {2, 4}, {3, 4}, {3, 5}, {4, 6}}
Output:1

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

• Определите функцию dfs(vector<vector<int> >& graph, int s, int e, vector<int> vis, int count, vector<int>& dp) и выполните следующие шаги:
  • Если s равно e , то это означает, что текущий путь является одним из возможных, запихнуть значение count в вектор dp[] и вернуться.
  • Переберите диапазон [0, graph[s]] , используя переменную i и выполнив следующие шаги:
    • Если vis[i] не равно 1, то установите значение vis[i] равным 1 и вызовите функцию dfs(graph, i, e, vis, count+1, dp), чтобы найти другие возможные пути и установить значение vis[0] снова возвращается к 0.
• Инициализируйте двумерный векторный граф[][] с N строками для хранения вершин, связанных с каждой вершиной.
• Переберите диапазон [0, M], используя переменную i , и выполните следующие шаги:
  • Поместите значение b-1 на векторный график[][] в строку a-1.
  • Поместите значение a-1 на векторный график[][] в строку b-1.
• Инициализируйте вектор vis[] размера N , чтобы отслеживать посещенные узлы.
• Инициализируйте вектор dp[] для хранения длины всех возможных путей.
• Вызовите функцию dfs(graph, 0, N-1, vis, 0, dp), чтобы найти все возможные пути и сохранить их в векторе dp[] .
• Отсортируйте вектор dp[] в порядке возрастания.
• Если размер вектора dp[] больше 1, верните значение dp[1]-dp[0] , иначе верните 0 в качестве ответа.

Ниже приведена реализация описанного выше подхода.

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

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

• Определите функцию get_edges(int s, vector<int>& edge, vector<int> p) и выполните следующие шаги:
  • Если s равно -1, то возврат.
  • Вызовите функцию get_edges(p[s], edge, p), чтобы найти все ребра на кратчайшем пути.
  • Вставьте значение s в векторные ребра [].
• Определите функцию dist_helper(vector<vector<int> > graph, vector<int>& d, int v1, int v2, int N) и выполните следующие шаги:
  • Инициализируйте вектор vis[] для отслеживания посещенных узлов.
  • Инициализируйте очередь пар q[] для выполнения поиска в ширину и поиска пути.
  • Поставьте пару {0, 0} в очередь пар q[].
  • Отметьте значение vis[0] как 1(visited) .
  • Повторяйте цикл while, пока очередь пар q[] не станет пустой.
    • Инициализируйте переменную a как начало очереди пар q[] и удалите элемент из очереди пар q[].
    • Переберите диапазон [0, graph[a.first]] , используя переменную i и выполнив следующие шаги:
      • Если i равно v1 и a.first равно v2 или i равно v2 и a.first равно v1, то продолжайте.
      • Если vis[i] равно 0, тогда установите значение d[i] как 1+a.second, p[i] как a.first и vis[i] как 1 и поставьте в очередь пару {i, d[ i]} в очередь пар q[].
• Определите функцию dist(vector<vector<int> > graph, vector<int>& d, vector<int> &p, int N) и выполните следующие шаги:
  • Инициализируйте вектор vis[] для отслеживания посещенных узлов.
  • Инициализируйте очередь пар q[] для выполнения поиска в ширину и поиска пути.
  • Поставьте пару {0, 0} в очередь пар q[].
  • Отметьте значение vis[0] как 1(visited) .
  • Повторяйте цикл while, пока очередь пар q[] не станет пустой.
    • Инициализируйте переменную a как начало очереди пар q[] и удалите элемент из очереди пар q[].
    • Переберите диапазон [0, graph[a.first]] , используя переменную i и выполнив следующие шаги:
      • Если vis[i] равно 0, тогда установите значение d[i] как 1+a.second и vis[i] как 1 и поставьте пару {i, d[i]} в очередь пар q [].
• Инициализируйте двухмерный векторный граф[][] с N строками для хранения вершин, связанных с каждой вершиной.
• Переберите диапазон [0, M], используя переменную i , и выполните следующие шаги:
  • Поместите значение b-1 на векторный график[][] в строку a-1.
  • Поместите значение a-1 на векторный график[][] в строку b-1.
• Инициализируйте векторы p[] и d[] размера N , чтобы отслеживать родительские узлы и длину путей.
• Вызовите функцию dist(graph, d, p, N), чтобы найти длину кратчайшего пути.
• Инициализируйте вектор Distances[] для хранения длины всех возможных путей.
• Вставьте значение d[N-1] в вектор расстояний[].
• Инициализируйте вектор edge[] , чтобы получить все ребра по кратчайшему пути.
• Вызовите функцию get_edges(N-1, ребра, p), чтобы найти все ребра на кратчайшем пути.
• Переберите диапазон [0, edge.size()-1] , используя переменную i , и выполните следующие шаги:
  • Вызовите функцию dist_helper(graph, d, ребра [i], ребра [i+1], N), чтобы найти все ребра на кратчайшем пути.
  • Вставьте значение d[N-1] в вектор расстояний[].
• Отсортируйте векторные расстояния [] в порядке возрастания.
• Если размер вектора расстояний[] больше 1, то верните значение расстояний[1]-расстояний[0] , иначе верните 0 в качестве ответа.

Ниже приведена реализация описанного выше подхода.

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