Для графа на рис.4 выполнить следующие задачи:
а) По алгоритму Дейкстры найти кратчайший путь от начальной вершины до всех других вершин (рис.4).
б) Построить древо кратчайших путей (рис.4).
в) Найти максимальный поток и минимальный разрез в транспортной сети, используя алгоритм Форда-Фалкерсона. Построить граф приростов. Проверить выполнение условий для максимальности построенного полного потока. Источник – вершина 1, сток – 6.
х1
4
х2
х3
х4
х5
х6
5
3
1
5
7
8
6
4
2
2
10
х1
4
х2
х3
х4
х5
х6
5
3
1
5
7
8
6
4
2
2
10
Рис.4 – Граф G
Решение
А) Воспользуемся алгоритмом Дейкстры нахождения критического пути.
Пусть задан взвешенный граф , неотрицательные веса на дугах которого будем интерпретировать как расстояния от вершины до вершины . Длиной пути называется сумма длин составляющих путь дуг. Требуется найти кратчайший путь из вершины в вершину .
В процессе работы алгоритма каждая вершина имеет метку, которая может быть временной или постоянной . Временная метка есть длина некоторого пути из в , возможно не оптимального. В процессе работы алгоритма временные метки могут изменяться, уменьшаясь, когда удается найти более короткий путь. На каждом шаге алгоритма вершина , имеющая минимальную временную метку получает постоянную метку . Постоянная метка есть длина кратчайшего пути из в , в дальнейшем она не меняется.
В начальный момент вершина имеет постоянную метку , а все остальные вершины графа – временные метки . На первом шаге алгоритма каждая вершина , для которой существует дуга , получает временную метку (помечается из вершины ). Затем вершина , для которой имеет минимальное значение, получает постоянную метку (если минимум достигается на нескольких вершинах, то берется любая из них). Кратчайший путь из в проходит по ребру .
На втором шаге алгоритма для каждой вершины , которая имеет временную метку и для которой существует дуга , вычисляется сумма и, если эта сумма меньше, чем , то вершина получает новую временную метку
(помечается из вершины ).
Затем среди всех вершин, имеющих временные метки, находится вершина , для которой имеет минимальное значение, и её временная метка делается её постоянной меткой .
Пусть – вершина, получившая на () – ом шаге постоянную метку
. Тогда на – ом шаге алгоритма для каждой вершины с временной меткой, для которой существует дуга , вычисляется сумма и, если эта сумма меньше чем , то вершина v получает новую временную метку
(помечается из вершины ). Затем среди всех вершин, имеющих временные метки, выбирается вершина с минимальной временной меткой и полагается .
Алгоритм заканчивает работу, когда вершина получает постоянную метку . Эта метка равна кратчайшему пути из в . Чтобы восстановить этот путь, нужно найти вершину, из которой была помечена вершина , затем вершину, из которой была помечена та вершина, и т.д., пока не дойдем до вершины . Тогда последовательность этих же вершин в обратном порядке и определит искомый кратчайший путь.
Рассмотрим работу алгоритма на примере нашего графа.
Работу алгоритма представим в виде таблицы 2, элемент на пересечении i – ой строки и j – го столбца которой есть метка вершины xj после i – го шага
Задать вопрос
на новый заказ в Автор24.
