Взвешенные графы и алгоритмы поиска кратчайшего пути.

До сих пор нас интересовали вершины и ребра графа, по которым можно перемещаться. Теперь нас будет интересовать, как наилучшим способом осуществить перемещение из точки А в точку В. Возникает вопрос, что значит «наилучшим способом». Это может быть самый дешевый путь. самый короткий путь, или путь, выбранный с каким – то другим критерием. В дальнейшем для общности мы будем говорить о наилучшем или кратчайшем пути. Для определения кратчайшего пути присвоим каждому ребру вес или меру. Если попытаться найти кратчайшее расстояние между двумя городами, то города можно интерпретировать как вершины графа, а веса как расстояния между городами, которые мы будем проезжать.Если найти самый дешевый способ перелета из одного города в другой, то вес ребер между вершинами, представляющими города, будет стоимостью перелета из города в город. Если прямого перелета из города в город нет, то не будет и ребра между соответствующими вершинами. Для упрощения в дальнейшем будем рассматривать вес ребра как расстояние между городами, а наилучший путь из точки А в точку В как кратчайший путь между А и В.

Определение.

Граф, каждому ребру которого поставлено в соответствие некоторое число, называется взвешенным графом. Число, поставленное в соответствие ребру, называется весом этого ребра.

Одной из важнейших задач в теории взвешенных графов является задача о кратчайшем соединении, основанная на применении алгоритма Краскала. Краскал (род. в 1928 г. в Нью-Йорке. рассматриваемый далее алгоритм был предложен Краскалом еще на втором курсе университета.

Теорема (алгоритм Краскала).

Последовательность дуг покрывающего дерева минимального веса мжожепт быть найдена с помощью следующего алгоритма:

1. v₁ – дуга наименьшего веса из всех имеющихся, не являющаяся петлей;
2. если уже определен начальный отрезок последовательности v₁, v₂,..., v_k-1, то дуга v_k

а) добавление дуги v_к не приводит к образованию цикла;

b) из всех дуг, удовлетворяющих условию а), дуга v_k - обладает наименьшим весом.

Применим алгоритм Краскала к графу, изображенному на рисунке. Пусть А, В, С, D, E, F – населенные пункты, линии – проектируемые участки дорог, цифры над линиями – их стоимость.

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

6 C

B 1

5 3

D

1 3 F 4 3

A E

В нашем случае выбираем v₁ = CD, v₂ = AB, v₃ = ED далее отпадает возможность выбора CE, т.к. приводит к образованию цикла. Далее v₄ = CF и отпадает возможность выбора EF, v₅ = AF, отпадает возможность выбора BC, BF, AE и процесс выбора дуг автоматически оборвался. Полученный путь изображен на рисунке. Пунктиром обозначены дуги, не вошедшие в этот маршрут. Полученный путь изображен на рисунке.

B C

5 1

1 F D

4 3 2

A E

Дата добавления: 2015-07-20