41. Алгоритм нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг — метод Дейкстры. Оценка вычислительной сложности.

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

Алгоритм нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг — метод Дейкстры

Данные: Ориентированный граф V, E с выделенным источником s  V, матрица весов дуг A [u, v], u, v  V (все веса неотрицательны).

Результаты: Расстояния от источника до всех вершин графа D[v] = d(s, v), vV.