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

Пусть 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, для которых (v) m. Если вершина и не помечена, значит, нет пути от s к u, меньше чем m+1. Если u связана ребром с вершиной, помечной,то ее пометка, во-первых, будет равна m+1, во-вторых, имеется путь длины m от s к данной вершине и, значит, длина кратчайшего пути от s к u равна m+1. Если u не связана ребром с вершиной, имеющей пометку m, то не существует пути, короче, чем m+1 от s к u, поскольку предыдущая вершина на этом пути имела бы пометку m.

Алгоритм ПУТЬ.

Полагаем i = (t) и помечаем v(i) = t.

Находим вершину u такую, что u связана ребром с v(i) и (u) = i-1. Помечаем v(i-1) = u.

Если i = 1, то останавливаемся, и уменьшаем i на 1 и повторяем шаг 2).

Приводимое ниже утверждение позволяет находить число путей фиксированной длины между любыми двумя вершинами.

Для графа G(V,E), | V | = u определим матрицу смежности, т.е. (n n) - матрицу A = (a_ij), i,j = l,...,u,где