Графы
4.1 Алгоритм Дейкстры (алгоритм расстановки меток)
Неформальное объяснение:
Каждой вершине из V сопоставим метку -- минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово -- на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.
Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин -- бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.
Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины. Для каждого соседа вершины u, кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.
Задание 2. По заданной матрице весов графа G найти величину минимального пути и сам путь от вершины до конечной вершины или по алгоритму Дейкстры.
1 итерация:
Присваиваем начальной вершине v1 значение l(v1)=0, всем остальным вершинам присваиваем .
2 итерация
Выделим все вершины
и припишем им числовые временные метки по формуле .
l(v2)=5
l(v3)=8
l(v4)=7
l(v5)=18
вершина v2 становиться постоянной
3 итерация:
Выделим все вершины и припишем им числовые временные метки по формуле .
l(v3)=8
l(v4)=7
l(v5)=18
вершина v4 становиться постоянной
4 итерация:
Выделим все вершины и припишем им числовые временные метки по формуле .
l(v3)=8
l(v5)=13
вершина v3 становиться постоянной
5 итерация:
Выделим все вершины и припишем им числовые временные метки по формуле .
l(v5)=13
l(v6)=24
вершина v5 становиться постоянной
6 итерация:
Выделим все вершины и припишем им числовые временные метки по формуле .
l(v6)=24
Алгоритм закончен. Результаты всех итераций зафиксированы в таблице 1
Кратчайший путь из v1 в v6: , l(v6)=24