Граф и его элементы

курсовая работа

4. Алгоритм Флойда-Уоршелл

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

Прежде чем представлять алгоритмы, необходимо ввести некоторые обозначения. Перенумеруем вершины исходного графа целыми числами от 1 до N. Обозначим через di,jm длину кратчайшего пути из вершинм i в вершину j, который в качестве промежуточных может содержать только первые m вершин графа. (Напомним, что промежуточной вершиной пути является любая принадлежащая ему вершина, не совпадающая с его начальной или конечной вершинами.) Если между вершинами i и j не существует ни одного пути указанного типа, то условно будем считать, что di,jm=?. Из данного определения величин di,jm следует, что величина di,j0, представляет длину кратчайшего пути из вершины i в вершину j, не имеющего промежуточных вершин, т. е. длину кратчайшей дуги, соединяющей i с j (если такие дуги присутствуют в графе). для любой вершины i положим di,im= 0. Отметим далее, что величина di,jmпредставляет длину кратчайшего пути между вершинами i и j.

Обозначим через Dm матрицу размера NxN, элемент (i, j) которой совпадает с di,jm. Если в исходном графе нам известна длина каждой дуги, то мы можем сформировать матрицу D0. Наша цель состоит в определении матрицы DN, представляющей кратчайшие пути между всеми вершинами рассматриваемого графа.

В алгоритме Флойда в качестве исходной выступает матрица D0. Вначале из этой матрицы вычисляется матрица D1. Затем по матрице D1 вычисляется матрицав D2 и т. д. Процесс повторяется до тех пор, пока по матрице DN-1 не будет вычислена матрица DN.

Рассмотрим основную идею, лежащую в основе алгоритма Флойда. Суть алгоритма Флойда заключается в проверке того, не окажется ли путь из вершины i в вершину j короче, если он будет проходить через некоторую промежуточную вершину m. Предположим, что нам известны:

1) кратчайший путь из вершины i в вершину m, в котором в качестве промежуточных допускается использование только первых (m - 1) вершин;

2) кратчайший путь из вершины m в вершину j, в котором в качестве промежуточных допускается использование только первых (m - 1) вершин;

3) кратчайший путь из вершины i в вершину j, в котором в качестве промежуточных допускается использование только первых (m - 1) вершин.

Поскольку по предположению исходный граф не может содержать контуров отрицательной длины, один из двух путей -- путь, совпадающий с представленным в пункте 3, или путь, являющийся объединением путей из пунктов 1 и 2 -- должен быть кратчайшим путем из вершины i в вершину j, в котором в качестве промежуточных допускается использование только первых m вершин. Таким образом,

di,jm=min{ di,mm-1+ dm,jm-1; di,jm-1}, (3)

где di,jm - элемент матрицы Dm, di,jm-1 - элементы матрицы Dm-1 найденой на предыдущем шаге алгоритма.

Из соотношения видно, что для вычисления элементов матрицы Dm необходимо располагать лишь элементами матрицы Dm-1. Более того, соответствующие вычисления могут быть проведены без обращения к исходному графу. Теперь мм в состоянии датьформальное описание алгоритма Флойда для нахождения на графе кратчайших путей между всеми парами вершин.

Алгоритм:

1) перенумеровать вершины графа от 1 до N целыми числами, определить матрицу D0, каждый элемент di,j которой есть длина кратчайшей дуги между вершинами i и j. Если такой дуги нет, положить значение элемента равным ?. Кроме того, положить значения диагонального элемента di,iравным 0;

2) для целого m, последовательно принимающего значения 1...N определить по элементам матрицы Dm-1элементы Dm;

3) алгоритм заканчивается получением матрицы всех кратчайших путей DN, N - число вершин графа. Для определения по известным элементам матрицы Dm-1 элементов матрицы Dm в алгоритме Флойда применяется рекурсивное соотношение указанное в формуле (3).

Делись добром ;)