Кратчайший путь в направленном ациклическом графе

Учитывая взвешенный ориентированный ациклический граф и исходную вершину в графе, найдите кратчайшие пути от данного источника ко всем остальным вершинам.

Для общего взвешенного графа мы можем вычислить кратчайшие расстояния от одного источника за время O (VE), используя алгоритм Беллмана – Форда. Для графика без отрицательных весов мы можем сделать лучше и рассчитать кратчайшие расстояния от одного источника за время O (E + VLogV), используя алгоритм Дейкстры. Можем ли мы сделать еще лучше для направленного ациклического графа (DAG)? Мы можем рассчитать кратчайшие расстояния от одного источника за время O (V + E) для DAG. Идея состоит в том, чтобы использовать топологическую сортировку.

Мы инициализируем расстояния до всех вершин как бесконечные, а расстояние до источника как 0, затем мы находим топологическую сортировку графа. Топологическая сортировка графа представляет собой линейное упорядочение графа (см. Ниже, рисунок (b) является линейным представлением рисунка (a)). Когда у нас есть топологический порядок (или линейное представление), мы последовательно обрабатываем все вершины в топологическом порядке. Для каждой обрабатываемой вершины мы обновляем расстояния до соседней вершины, используя расстояние до текущей вершины.

Следующий рисунок взят из этого источника. Он показывает пошаговый процесс поиска кратчайших путей.

Ниже приведен полный алгоритм поиска кратчайших расстояний.
1) Инициализировать dist [] = {INF, INF,….} И dist [s] = 0, где s - исходная вершина.
2) Создайте топологический порядок всех вершин.
3) Проделайте следующее для каждой вершины u в топологическом порядке.
……… .. Проделайте следующее для каждой смежной вершины v из u
……………… if (dist [v]> dist [u] + weight (u, v))
……………………… расст [v] = расст [u] + вес (u, v)

Following are shortest distances from source 1
INF 0 2 6 5 3 

Сложность времени: сложность времени топологической сортировки составляет O (V + E). После определения топологического порядка алгоритм обрабатывает все вершины и для каждой вершины запускает цикл для всех смежных вершин. Общее количество смежных вершин в графе равно O (E). Таким образом, внутренний цикл выполняется O (V + E) раз. Следовательно, общая временная сложность этого алгоритма составляет O (V + E).

Использованная литература:
http://www.utdallas.edu/~sizheng/CS4349.d/l-notes.d/L17.pdf

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не переставай учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.