Лекция 8.5. Графы, алгоритм Дейкстры

Граф состоит из множества вершин V и множества рёбер E. Элементы множества рёбер – пары вида (a, b), где a и b принадлежат множеству вершин V. Каждое такое ребро обозначает связь между двумя вершинами.

Примером графа из жизни являются города (вершины) и дороги между ними (рёбра). Причём дорога из города a в город b должна быть обязательно одна.

_images/graph1.png

Графы могут быть направленными или ненаправленными. Ненаправленными графами считаются те, в которых связь между рёбрами симметрична, например, все дороги двусторонние и по ним можно ехать в обоих направлениях. Примером направленного графа можно считать карту местности, на которой есть хотя бы одна односторонняя дорога.

Направленные графы являются более общими математическими объектами, и любой ненаправленный граф можно представить в виде направленного графа, у которого для каждого ребра \((a, b) \in E\) существует обратное ребро \((b, a) \in E\). Поэтому все алгоритмы, работающие для направленных графов, работают и на ненаправленных.

Так же во многих практических применениях рассматриваются взвешенные графы. В таких графах каждому ребру сопоставлен определённый вес. Как пример взвешенного графа можно рассмотреть, дороги между городами, где каждой дороге сопоставлено определённое число, длина дороги или время проезда по ней. Такие графы используются в навигаторах для определения кратчайших маршрутов. В этой главе мы рассмотрим один из алгоритмов определения кратчайшего маршрута из одной вершин графа во все остальные.

Пример ориентированного графа с весами:

_images/graph2.png

Представление графов в памяти компьютера

В множестве вершин V, состоящем из N вершин обычно каждую вершину представляют как целое число от 0 до N - 1 включительно. То есть, просто нумеруют вершины от 0.

С представлением рёбер E возможно большее разнообразие и существует три вида представлений:

  1. Представление в виде списка всех рёбер. Ребро – это тройка (i, j, w), где i и j – вершины из диапазона от 0 до N - 1 включительно. w – вес ребра (i, j)
  2. Представление в виде матрицы смежности. Представлена в памяти в виде двумерного массива arr2d размером N на N. Элемент arr2d[i][j] хранит значение 1, если ребро (i, j) есть, и 0, если такого ребра нет. Веса можно хранить отдельно в ещё одном двумерном массиве такого же размера, либо в этом же массиве arr2d вместо единиц, но тогда для указания отсутствия рёбер вместо нулей придётся хранить какое-нибудь другое значение, например, None, чтобы не спутать нулевой вес с отсутствием вершины.
  3. Представление в виде списков смежности. Список neighbours[i] описывает все рёбра, выходящие из вершины i и содержит пары (j, w), где j – смежная с i вершина, а w – вес ребра (i, j).

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

Так же во всех представлениях не нужно забывать, что при вводе неориентированного графа нужно добавлять как прямое ребро (i, j, w), так и обратное (j, i, w). Тогда алгоритмы, рассчитанные на ориентированные графы будут корректно работать и с неориентированными.

Алгоритм Дейкстры

Путь на графе – это последовательность вершин \(u_0\), ..., \(u_{n-1}\), такая что для любых двух соседних вершин из этого пути \(u_{i}\), \(u_{i+1}\) в графе существет ребро, соединяющее их.

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

На входе:

V
Множество вершин (если вершины нумеруются цифрами, достаточно числа вершин N).
E
множество рёбер с их весами
a
начальная вершина

На выходе:

dist
массив, в котором dist[i] – длина кратчайшего пути из вершины a в вершину i

Медленный вариант алгоритма за время \(O(N^{2})\) (линейный поиск в массивах dist и visited):

dist = массив из N элементов
заполнить все элементы dist значением "бесконечность"
dist[a] = 0
visited = массив из N элементов
заполнить все элементы значением "ложь"
цикл N раз {
    u = вершина с минимальным dist[i] и ложным visited[i]
    цикл по всем вершинам v, смежным с вершиной u {
        если dist[v] > dist[u] + вес(u, v) {
            dist[v] = dist[u] + вес(u, v)
        }
    }
    visited[u] = истина
}

Более быстрый вариант предполагает использование очереди с приоритетами на основе бинарной кучи и имеет время работы O(N * log(N)).