От 1-го до K-го кратчайшего пути от узла 1 до N в данном графе

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

Для заданного ориентированного и взвешенного графа из N узлов и M ребер задача состоит в том, чтобы найти кратчайшие пути от 1- го до K -го кратчайшего пути от узла 1 до N .

Примеры:

Input: N = 4, M = 6, K = 3, edges = {{1, 2, 1}, {1, 3, 3}, {2, 3, 2}, {2, 4, 6}, {3, 2, 8}, {3, 4, 1}}
Output: 4 4 7
Explanation: The shortest path length from 1 to N is 4, 2nd shortest length is also 4 and 3rd shortest length is 7.

Input: N = 3, M = 3, K = 2, edges = {{1, 2, 2}, {2, 3, 2}, {1, 3, 1}}
Output: 1 4

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

  • Инициализируйте приоритетную очередь, скажем, pq размера N для хранения номера вершины и значения расстояния.
  • Инициализируйте двумерный вектор, скажем, dis размера N*K и инициализируйте все значения очень большим числом, скажем, 1e9.
  • Установите dis[1][0] в ноль, значение расстояния исходной вершины.
  • Итерировать, пока pq не пуст.
    • Извлеките значение из pq и сохраните значение вершины в переменной u и расстояние до вершины в переменной d.
    • Если d больше, чем расстояние u , то продолжайте.
    • Для каждой соседней вершины v вершины u проверьте, больше ли значение K -го расстояния, чем вес uv плюс значение расстояния u, затем обновите значение K-го расстояния v и отсортируйте k расстояний вершины v.

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

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

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