Для графа на рис.4 выполнить следующие задачи: а) По алгоритму Дейкстры найти кратчайший путь от

Для графа на рис.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 – го шага