Нахождение кратчайших путей между парами вершин

Алгоритмы, вычисляющие остовые деревья минимальной стоимости.

Представление графов

Выбор структуры данных для графа зависит от сложности решаемой задачи. Широко известны два способа представления графов – это матрица смежности и список смежности.

Матрица смежности – это матрица a[n, n], где n – это число элементов, а сами элементы a[i, j] равны значению метки дуги (i, j), если есть дуга из вершины i в вершину j.

Список смежности – это массив, который состоит из списков всех вершин, для каждой их которых приведены вершины смежные с ней.

Представление орграфов. Если имеется орграф (рис. 16.3), то его можно представить в виде матрицы смежности (рис. 16.4) или в виде списка смежности (рис.16.5).

Представление графов. Если имеется граф (рис. 14.6), то его можно представить в виде матрицы смежности (рис. 14.7) или в виде списка смежности (рис.14.8).

Если g=(v, e) – это помеченный граф, то остовое дерево– это такое дерево, которое содержит все вершины v графа g. Стоимость остового дерева равна сумме стоимостей всех рёбер, которые входят в него. Тогда остовым деревом минимальной стоимости является дерево, у которого стоимость минимальна (рис. 16.9).

Известны два алгоритма вычисляющие остовые деревья минимальной стоимости. Это алгоритм прима и алгоритм крускала.

Принцип алгоритма прима.Формируется граф, потом из множества его дуг v выбираются наименьшие по величине метки, тогда как их начала копируются во множество u, пока u не станет равно множеству v.

Так, например, для графа (рис. 16.6) сначала была выбрана дуга 3→5, потом 4 →5, затем 2 →5 и, наконец, 1 →2. Т.е. Множество u={3, 4, 2, 1, 5}.

Принцип алгоритма крускала.Формируется граф. Из него выбирают минимальные компоненты, т.е дуги с минимальной по величине меткой. Сначала эти компоненты не соединены, но в процессе работы алгоритма они соединяются в остовое дерево минимальной стоимости. Данный алгоритм применяется на графах с большим числом дуг и вершин. Условием получения дерева минимальной стоимости может стать равенство u=v, как в предыдущем алгоритме.

Задачей нахождения кратчайших путей является определение для любой пары вершин (v, w) такого пути от вершины v в вершину w, который был бы минимальным среди всех возможных путей от v к w.

Пример такой задачи – это составление расписания перелётов по маршрутам, которые связывают различные города. Результатом расчётов будет минимальное время перелёта из одного заданного города в другой.

Существуют два алгоритма определения кратчайшего пути – это алгоритм дейкстры и алгоритм флойда.

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

Принцип алгоритма флойда. В результате решения задачи вычисляется матрица a[i, j] длин кратчайших путей между концевыми вершинами пути i и j, где матрица a имеет размер nrn. Здесь n – это число узлов графа, а элементы матрицы – это величины меток дуги. Подробно принцип работы этих двух методов разобран в лабораторной работе №7.