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

/* ВЫЧИСЛЕНИЕ ПУТЕВОЙ МАТРИЦЫ ПО ЗАДАННОЙ МАТРИЦЕ СМЕЖНОСТИ */ #include <stdio.h> void pm(int A[][5],int P[][5],int n); int main() { int i,j,n;

Ниже демонстрируется получение путевой матрицы из матрицы смежности. Здесь из-за особенностей языка Си к принимает значения 0, 1, ...,«- 1.

Алгоритм реализуется посредством трех вложенных циклов по к, i и j, имеет временную сложность О(п3).

2)есть пути между вершинами / и к и одновременно между вершинами к и у, проходящие через вершины с номерами, меньшими к.

Таким образом, после &-го прохода путь между вершинами / и j есть тогда и только тогда, если:

Рис. 8.7. Схема определения элемента матрицы

Алгоритм выполняется за п проходов. После к-го прохода ру содержит 1 или 0 в зависимости от того, имеются ли пути между вершинами i и j, которые не проходят через вершины с номерами, большими или равными к, т.е. между вершинами / и j могут быть вершины только с номерами, меньшими или равными к. Это представлено на рис. 8.7.

Рассмотренный способ определения путевой матрицы Рп из матрицы В" громоздок. Более рациональный способ получения путевой матрицы предложен Уоршаллом [8], в котором используются реализуемые просто булевы операции. В этом алгоритме вначале путевая матрица Р устанавливается равной матрице смежности, затем за к проходов, к=1,2,...,п, в циклах по i nj выполняются булевы операции:

Путевая матрица только показывает, имеется или отсутствует путь между парой вершин (или цикл в любой вершине), но не определяет все пути.

Если нас интересует, достижима ли вершина v, из вершины v, и не интересует число путей из вершины v, в vj, то достаточно в матрице В" все ненулевые элементы поменять на 1. Тогда получим матрицу достижимости, или путевую матрицу Рп* , элементы которой ру = 1, если существует путь из v, в vy, и ру = 0 в противном случае. Матрицу Р называют также транзитивным замыканием матрицы смежности.

8.4.Путевая матрица (матрица достижимости)

Элемент by показывает число существующих путей из v,- в V/ длиной, меньшей или равной (я-1). Если элемент Ьу>0, то вершина v,достижима из v,. Матрица В"=А+А2+А*+...А" дает возможность определить число элементарных путей и элементарных циклов в графе, представленном матрицей смежности А.

Если мы хотим определить, существует ли в графе с п верцшW! нами путь из v, в v,-, то нам необходимо проверить, имеются лЩ элементарные пути длиной, меньшей или равной (л - 1). Такие пути определяются с помощью матрицы

ДЛИНОЙ Г ИЗ V/ В Vj.

Аналогично элемент ау матрицы АТ задает число путей ДОИДь ной 3 из v, в Vj, а по матрице Ат мы можем определить число путей

Для каждого к условие atk*akj - 1 выполняется тогда и толькo тогда, когда оба элемента а^ и а^-равны 1, т.е. имеются ребрйц (Vj,Vk) и (vk,vj), следовательно, существует путь из v,-в Vy длиной 2 через v^. Тогда приведенная выше сумма равна числу различш путей длиной 2 из v, в vj через различные вершины vk.

Рассмотрим матрицу смежности. Единица в /-й строке и j-м столбце матрицы А, т.е. ау=1, указывает на наличие ребра (v,,Vj)k т.е. на путь длиной 1 из V,B VJ. Элементами матрицы А2 будут;

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

   3. Пути в графе

Алгоритмы на графах