Разработка системы задач (алгоритмы-программы) по дискретной математике — страница 5
используется не более одного раза. Элементарный путь - это путь, в котором каждая вершина используется не более одного раза. Если существует путь из вершины графа v в вершину i, то говорят, что i достижима из v. Матрицу достижимости определим следующим образом: 1, если вершина i достижима из v и R[v,u]=0, при недостижимости Множество R(v) - это множество таких вершин графа G, каждая из которых может быть достигнута из вершины v. Обозначим через F(v) множество таких вершин графа G, которые достижимы из v с использованием путей длины 1. T2(v) - это Г(Г(у)), то есть с использованием путей длины 2 и так далее. В этом случае: R(v)={v}UГ(v)UГ2(v)U...UГp(v). При этом р - некоторое конечное значение, возможно, достаточно большое. Пример (для рисунка). R(1)={1}U{2,5}U{1,6}U{2,5,4}U{1,6,7}={1,2,4,5,6,7} Выполняя эти действия для каждой вершины графа, мы получаем матрицу достижимостей R. Кратчайшие пути. Алгоритм Дейкстры Дано. Ориентированный граф G=<V,E>, s - вершина источник; матрица смежности A (A:array[1..n,1..n] of integer); для любых u, v€V вес дуги неотрицательный (А[u,v]>=0). Результат. Массив кратчайших расстояний - D. В данном алгоритме формируется множество вершин Т, для которых еще не вычислена оценка расстояние и, это главное, минимальное значение в D по множеству вершин, принадлежащих Т, считается окончательной оценкой для вершины, на которой достигается этот минимум. С точки зрения здравого смысла этот факт достаточно очевиден. Другой "заход" в эту вершину возможен по пути, содержащему большее количество дуг, а так как веса неотрицательны, то и оценка пути будет больше. Пример Его матрица смежности: ∞ 3 7 ∞ ∞ ∞ 1 ∞ 2 ∞ ∞ 1 А= ∞ 1 ∞ 4 4 ∞ ∞ ∞ ∞ ∞ 1 5 ∞ ∞ 1 ∞ ∞ 3 ∞ ∞ ∞ 2 ∞ ∞ В таблице приведена последовательность шагов (итераций) работы алгоритма. На первом шаге минимальное значение D достигается на второй вершине. Она исключается из множества Т, и улучшение оценки до оставшихся вершин (3,4,5,6) ищется не по всем вершинам, а только от второй. № итерации D[1] D[2] D[31 D[4] D[5] D[6] T 1 0 3 7 ∞ ∞ ∞ [2,3,4,5,6] 2 0 3 5 ∞ 11 4 [3,4,5,6] 3 0 3 5 6 ∞ 4 [3,4,5] 4 0 3 5 6 9 4 [4,5] 5 0 3 5 6 7 4 [5] Время работы алгоритма пропорционально N2. Алгоритм Флойда (кратчайшие пути между всеми парами вершин). Дано. Ориентированный граф G=<V,E>, s - вершина источник; матрица смежности A (A:array[1..n,1..n] of integer); для любых u, v€V вес дуги неотрицательный (А[u,v]>=0). Результат. Матрица D кратчайших расстояний между всеми парами вершин графа и кратчайшие пути. Идея алгоритма. Обозначим через Dm[i,j] оценку кратчайшего пути из i в j с промежуточными вершинами из множества [1..m]. Тогда имеем: D0[i,j]:=A[i,j] и D(m+1)[i,j]=min{Dm[i,j],Dm[i,m+1]+Dm[m+1,j]}. Второе равенство требует пояснения.
Похожие работы
- Рефераты
- Контрольные