10.5. Задача поиска кратчайшего пути в графе

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

Асимптотическая сложность нахождения компонент связности в графе — O(V+E), где V — число вершин, а E — число рёбер и дуг.

Опишем принцип работы алгоритма Дейкстры:

• Шаг 1. Всем вершинам, за исключением первой, присваивается вес равный бесконечности, а первой вершине — 0.
• Шаг 2. Все вершины не посещены.
• Шаг 3. Первая вершина объявляется текущей.
• Шаг 4. Вес всех невыделенных вершин пересчитывается по формуле: вес невыделенной вершины есть минимальное число из старого веса данной вершины, суммы веса текущей вершины и веса ребра, соединяющего текущую вершину с невыделенной.
• Шаг 5. Среди невыделенных вершин ищется вершина с минимальным весом. Если такова не найдена, то есть вес всех вершин равен бесконечности, то маршрута не существует. Следовательно, выход. Иначе, текущей становится найденная вершина. Она же выделяется.
• Шаг 6. Если текущей вершиной оказывается конечная, то путь найден, и его вес есть вес конечной вершины.
• Шаг 7. Переход на шаг 4.

Пример работы алгоритма показан на картинке ниже.

Посмотрим на реализацию.

Dijkstra(graph, start, finish, used):
    vector d(n, inf), p(n, -1)
    n = len(graph)
    graph[v] = 1
    for (int i = 0; i < n; ++i)
      int v = -1
      for (int j = 0; j < n; ++j)
        if (!used[j] and (v == -1 or d[j] < d[v]))
          v = j
      used[v] = true
      for (int j = 0; j < len(graph[v]); ++j)
        to = graph[v][i].vertex
        len = graph[v][i].edge
        if (d[v] + len < d[to])
          d[to] = d[v] + len
          p[to] = v

Асимптотическая сложность алгоритма Дейкстры — , где — число вершин, а — число рёбер и дуг.

✒️ Упражнение:
Подумайте, как восстановить путь используя введённый массив p?

✒️ Упражнение:
Как изменится кратчайший путь, если все веса рёбер увеличить на какое-то число?

✒️ Упражнение:
Как изменится кратчайший путь, если все веса рёбер увеличить в какое-то число раз?

✒️ Упражнение:
Подумайте, почему алгоритм работает только для графов без рёбер отрицательного веса?