15. Метод Дейкстры. (!)

Задача маршрутизации.

Алгори́тм Де́йкстры — алгоритм на графах. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации OSPF и IS-IS.

Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.

16. Метод Форда Фалкерсона. (!)

Алгоритм Форда-Фалкерсона. Поток в сети.

Определение 1:

          Сетью называется связный орграф без петель.

Определение 2:

          Потоком в сети называется некоторая функция, которая ставит в соответствие дуге некоторое число-вес дуги.

Для определения потока в сети используют алгоритм Форда-Фалкерсона:

а) ищем любую цепь из истока графа в сток;

б) каждой дуге приписываем возможный больший поток (наименьшее значение дуги) из истока в сток (записываем его через дробь с весом дуги; при этом поток не может превысить вес дуги, но может быть ему равен);

в) если поток становится равен весу дуги, то эта дуга является насыщенной, то есть через нее нельзя пройти при рассмотрении цепей в графе;

г) так перебираем все возможные цепи, пока станет невозможно попасть из истока в сток;

д) поток  в сети будет равен сумме потоков всех дуг, инцидентных стоку графа (следует заметить, что сумма потоков всех дуг, инцидентных стоку графа равна сумме потоков всех дуг, инцидентных истоку графа).

17. Другие задачи которые можно решить с помощью графов (примеры). (!)

Поиск A* (произносится «А звезда» или «А стар», от англ. A star) — алгоритм который находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной).

Алгоритм Джонсона позволяет найти кратчайшие пути между всеми парами вершин взвешенного ориентированного графа. Алгоритм Диница — полиномиальный алгоритм для нахождения максимального потока в транспортной сети.

Алгоритм ближайшего соседа — один из простейших методов решения задачи коммивояжёра. 

Алгоритм Косарайю (в честь американского учёного индийского происхождения Самбасивы Рао Косарайю (англ.)русск.) — алгоритм поиска компонент сильной связности в орграфе. 

Алгоритм Мальгранжа — разбиение графов на сильно связные под-графы.

Алгоритм Флойда — Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенногоориентированного графа.