Из предыдущего следует, что процесс нельзя продолжать тогда и только тогда, когда мы попадем в вершину a, причем степень вершины a относительно непройденных ребер равна нулю. Докажем, что в этом случае построенный цикл m - простой цикл. Покажем, что m содержит все ребра графа G. Если не все ребра графа G принадлежат m, то не принадлежащие m ребра порождают компоненты связности C1, …, Cm (m³1) в подграфе
2. НАХОЖДЕНИЕ КРАТЧАЙШИХ ПУТЕЙ В ГРАФЕ
Рассматрим ориентированные графы G(X, E) каждой дуге eÎE которого ставится в соответствие вещественное число l(e). Т.е. на множестве Е создана функция l:E®R. Такой граф принято называть нагруженным. Само число l называется весом дуги.
Можно увидеть аналогию между, например, картой автомобильных или железных дорог. Тогда множество вершин Х будет соответствовать городам, множество дуг – магистралям, соединяющим города, а веса – расстояниям. (На практике, при этом, фактически получится неориентированный граф).
В связи с изложенной аналогией будем называть веса дуг расстояниями.
Определение 2.1. Пусть имеется последовательность вершин x0, x1, …, xn, которая определяет путь в нагруженном графе G(X, E), тогда длина этого пути определяется как
Естественный интерес представляет нахождение кратчайшего пути между двумя заданными вершинами x и y.
Алгоритм Форда отыскания кратчайшего пути.
Будем предполагать, что все расстояния в графе положительны. (Если это не так, то ко всем весам можно всегда добавить такую константу, что все эти веса станут положительными).
Пусть мы ищем путь от вершины x0 к вершине xn. Будем каждой вершине xi ставить в соответствие некоторое число li по следующим правилам.
1° Положим l0= 0, li= ¥ (достаточно большое число) для "i > 0.
2° Ищем в графе дугу (xi, xj) удовлетворяющую следующему условию
lj - li > l(xi, xj), (1)
после чего заменяем lj на
Пункт 2°повторяется до тех пор, пока невозможно будет найти дугу, удовлетворяющую условию (1). Обоснуем этот алгоритм и укажем как определяется кратчайший путь.
Отметим, что ln монотонно уменьшается, то после завершения алгоритма найдется дуга , такая, что
По этой же самой причине найдется вершина , такая , что
этот процесс может продолжаться и дальше, так что получится строго убывающая последовательность
Покажем, что
Возьмем произвольный путь
После завершения алгоритма имеем следующие соотношения
Сложив все эти неравенства, получим
что и требовалось доказать.
Рассмотрим пример.
Рис. 2.1
На рис. 2.1а изображен исходный помеченный граф и начальные значения li. На рис. 2.1б для того же графа указаны конечные значения li и выделен кратчайший путь. Пометка вершин графа происходила в следующем порядке (в скобках указана дуга, вдоль которой выполняется (1)):
l1 = 6 (x0, x1),
l2 = 7 (x0, x2),
l3 = 6 (x0, x3),
l4 = 12 (x1, x3),
l4 = 11 (x2, x4),
l5 = 16 (x3, x4),
l5 = 15 (x4, x5),
l6 = 18 (x4, x6),
l6 = 17 (x5, x6).
Иногда возникает задача отыскания кратчайших расстояний между всеми парами вершин. Одним из способов решения этой задачи является
Обозначим lij длину дуги (xi, xj), если таковой не существует примем lij = ¥, кроме того, положим lii = 0. Обозначим
Уравнение (2) очевидно. Обоснуем уравнение (3). Рассмотрим кратчайший путь из xi в xj с промежуточными вершинами из множества {x1, …, xm, xm+1}. Если этот путь не содержит xm+1, то
Уравнения (2) и (3) позволяют легко вычислить матрицу расстояний [dij] между всеми парами вершин графа G(X, E). На первом этапе согласно (2) составляем n´n матрицу
Отметим, что алгоритм Флойда непосредственно не указывает сам кратчайший путь между вершинами, а только его длину. Алгоритм Флойда можно модифицировать таким образом, чтобы можно было находить и сами пути. Для этого получим вспомогательную матрицу [Rij], которая будет содержать наибольший номер вершины некоторого кратчайшего пути из xi в xj (Rij=0, если этот путь не содержит промежуточных вершин).