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

Алгоритм Дейкстры позволяет найти кратчайшие матрицы и их длину между конкретной вершиной и всеми остальными. Дан взвешенный орграф . Начало : , постоянная. , временная, . Текущая вершина p:=s. Итерация: . Просмотр — временные. Если , то , иначе ничего не меняется и переходим к следующей вершине. Правило появления постоянных меток: . Ищется v*: , тогда — постоянная.

Неформальное объяснение

1.Расстояние до источника 0-вершинаW, до всех остальных вершин (создаем метки).

2.В соответствии с весом всех вершин в которые есть пути из W объявляем метки. Значение метки-сумма меткиа меньше . W и длины пути из W в рассматриваемую вершину.(только если сумма меньше предыдущего значения метки)

3. Выбираем новое W в соответствии с минимальной меткой. Старое W помечено посещенным. Перейти на шаг 2, если все вершины посещены в шаг 4.

4. Метка элементов-кратчайшие расстояния из выбранной изначально вершины до всех остальных.

32. Алгоритм поиска в глубину в простом графе.

1. Просмотреть массив лидеров и сформировать множество вершин графа. В нём хранятся ещё необработанные вершины графа. Необходимо помнить, какие вершины из её списка смежности уже обработаны. Поэтому формируется массив с длиной , где хранятся номера первых ещё не обработанных алгоритмом вершин списка смежности . Положим стек вершин STACK, список вершин фундаментального цикла Cycle, множества древесных рёбер Tree, обратных рёбер Back пустыми. Обнулить массив D-номеров. Задать . Счётчик D-номеров count:=1.

2. if goto 2; else goto 8;

3. if goto 3; else выбрать из любую вершину, , goto 3;

4. Поместить v в STACK. Присвоить v D-номер . count++; goto 4;

5. Проверить по элементу , не достигнут ли конец списка смежности текущей вершины v. Если в списке смежности есть ещё не обработанные вершины, получить из него очередную вершину w, ++; goto 6; Если полностью обработан, удалить v из стека и goto 5;

6. if goto 1; else ; goto 4;

7. if ; goto 3; else goto 7;

8. if поместить w в Cycle. Читать содержимое стека, начиная с его вершины, до появления w и помещать в список Cycle (включая w), т.е. формировать фундаментальный цикл, соответствующий обратному ребру goto 4;

9. Закончить работу.

Для орграфа алгоритм выглядит чуть сложнее. В классификацию дуг добавляются прямые (от подлинного предка к подлинному потомку; ) и поперечные дуги (не древесные, не прямые, не обратные; между ветвями деревьев; ).

33. Алгоритм поиска в ширину в ориентированном графе.

Вход. Граф G = (V, E), заданный списками смежности; v₀ — начальная вершина (не обязательно первый элемент массива лидеров).

Выход. Массив М меток вершин, где каждая метка равна длине пути от v₀ до v.

0. Очередь Q положить пустой (Q = Ø). Все вершины пометить как недостижимые из вершины v₀, присваивая элементам массива М значение +∞ (М[v_i] = +∞, i = 1, N). Стартовую вершину v₀ пометить номером 0, т.е. длину пути от стартовой вершины v₀ до самой себя положить равной 0 (M[v₀] = 0). Поместить вершину v₀ в очередь Q. Перейти на шаг 1.

1. Если очередь Q не пуста (Q = Ø), то из „головы" очереди извлечь (с удалением из очереди) вершину u и перейти на шаг 2. Если очередь пуста, перейти на шаг 3.

2. Если список смежности L(u) вершины u пуст, вернуться на шаг 1.

Если список смежности L(u) вершины u не пуст, для каждой вершины w из списка смежности, где М[w] = +∞, т.е. вершины, которую еще не посещали, положить длину пути из стартовой вершины v₀ до вершины w равной длине пути от v₀ до вершины

и плюс одна дуга (М[w] = М[u] +1), т.е. отметить вершину w и поместить ее в очередь Q. После просмотра всех вершин списка смежности L(u) вернуться на шаг 1.

3. Распечатать массив М. Закончить работу.