Кратчайшие пути.

Пусть G(V, E) - конечный неориентированный граф и пусть заданы две его вершины s и t. Требуется найти кратчайший путь (длина пути равна числу входящих в него ребер) от вершины s к вершине t. Сначала мы опишем алгоритм, который находит длину кратчайшего пути.

Алгоритм ДЛИНА

1) Помечаем вершину s пометкой 0. Полагаем i = 0.

2) Находим все непомеченные вершины, связанные ребром с вершинами, имеющими оплетку i- Если таких вершин нет, t недостижимо из s, стоп. Если такие вершины есть, помечаем их i+1.

3) Если вершина t помечена, переходим к 4) Если нет, то увеличиваем i на 1 и повторяем шаг 2).

4)Длина кратчайшего пути от s к t равна i+1, стоп.

Корректность алгоритма следует из следующего утверждения.

Факт1. Вершина v графа G(V, E) помечается в алгоритме пометкой (v) тогда и только тогда, когда длина кратчайшего пути от вершины s к v равна (v).

Доказательство индукцией по i. Ясно, что при i=0, (v)=0 влечет v=s и утверждение справедливо. Предположим, что утверждение верно для всех вершин v, для которых . Если вершина u не помечена, значит нет пути от s к u, меньше чем m+1. Если и связана ребром с вершиной, помечной, то ее пометка, во-первых, будет равна m+1, во-вторых, имеется путь длины m от s к данной вершине и, значит, длина кратчайшего пути от s к u равна m+1. Если и не связана ребром с вершиной, имеющей пометку m, то не существует пути, короче, чем m+1 or s к u, поскольку предыдущая вершина на этом пути имела бы пометку m.

Сделаем к данному алгоритму дополнительные замечания.

1.