Тема 2.14. Методы решения сетевых задач.

Оглавление | Назад | Далее | Глоссарий понятий

Нахождение минимального остова в графе

Алгоритм решения

1. Упорядочить ребра графа по возростанию весов;
2. Выбрать ребро с минимальным весом, не образующее цикл с ранее выбранными ребрами. Занести выбранное ребро в список ребер строящегося остова;
3. Проверить, все ли вершины графа вошли в постоенный остов. Если нет, то выполнить пункт 2.

Продемонстрируем приведенный выше алгоритм на примере.

Пример 2.14.1

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

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

Можно дать много практических интерпретаций задачи о кратчайших путях. Например, вершины могут соответствовать городам и каждая дуга - некоторому пути, длина которого представлена весом дуги. Мы ищем кратчайшие пути между городами. Вес дуги может соответствовать стоимости (или времени) передачи информации между вершинами. В этом случае мы ищем самый дешевый (или самый скорый).

Данная задача может быть разбита на две:

1. для начальной заданной вершины найти все кратчайшие пути от этой вершины к другим;
2. найти кратчайшие пути между всеми парами вершин.

Рассмотрим алгоритм решения для задачи первого типа:

Необходимо найти путь от s - начальной вершины до t - конечной вершины. Каждой вершине присваиваем пометки I(Xi).

1. I(s) = 0, I(Xi) равно бесконечности для всех Хi не равных s и считать эти пометки временными. Положить р = s.
2. Для всех Хi, пренадлежащих Г(р) и пометки которых временны, изменить пометки по следующему правилу:
   I(Xi) = min[I(Xi), I(p) + c(p, Xi)]
3. среди всех вершин с временными пометками найти такую, для которой I(Xi*) = min[I(Xi)]
4. считать пометку вешины Хi* постоянной и положить р = Хi*.
5. если р = t, то I(р) является длинной кратчайшего пути, если нет, перейти к шагу 2.

Как только все пометки расставлены, кратчайшие пути получают, используя состношение I(Xi') + c(Xi',Xi) = I(Xi) (1). Поясним работу данного алгоритма на примере.

Пример 2.14.2

Для решения задачи второго типа можно применять данный алгоритм для каждой вершины.

Упражнения

Оглавление | Назад | Далее | Глоссарий понятий