92. Какую задачу решает алгоритм Дейкстры и в чем идея этого алгоритма?

• Дан орграф G = (V, E), матрица длин ребер {b_ij} (если ребра нет, b_ij = ).

Ограничение: длина всех ребер неотрицательная.

• Даны две вершины X и Y.

• Построить кратчайший путь из X в Y.

• Основная идея: использовать ту же формулу пересчета, что в алгоритме Флойда, но рассматривать только те вершины, которые лежат на путях, выходящих из X.

• Трудоемкость: T(N, M) = O(N²).

Построение минимального расстояния между вершинами.

Идея: Hа каждом шаге пытаемся уменьшить кратчайшее расстояние до непросмотренных вершин, используя очередную вершину, длину пути к которой уменьшить уже нельзя.

93. Какова трудоемкость алгоритмов Флойда и Дейкстры?

Трудоёмкость алг. Флойда T(n,m)=O(n^3), т. к. на каждом К-м шаге обсчитываем мат-цу (n*n) и для каждой вершины. Трудоёмкость Дейкстры: T(n,m)= O(n^2), т.к. на каждой итерации нужно просмотреть число вер-н(n), чтобы включить все вер-ны нам нужно n итераций.

Алгоритм Флойда в среднем работает быстрее, если нам нужно найти все расстояния.

94. Что такое поток в сети?

Потоком в транспортной сети Т называется неотрицательная вещественная функция, определенная на множестве дуг, удовлетворяющая условиям:

ограниченности: поток по любой дуге сети не превосходит пропускной способности этой дуги;

сохранения: суммарный поток, заходящий в любую вершину сети (кроме истока и стока) равен суммарному потоку, выходящему из этой вершины.

Дуга сети называется насыщенной, если поток по этой дуге равен пропускной способности этой дуги.

Поток по пути называется полным, если хотя бы одна дуга пути насыщена.

95. Чем отличаются источник и сток от остальных вершин?

От источника существуют пути, а к источнику нет пути, к стоку ведут пути, а из стока нет пути

S- исток(источник чего-либо); T –сток (там, где потребляется).

Источник – это вершина двуполюсного оргафа, которой инцидентны только исходящие дуги.

Сток – это вершина двуполюсного оргафа, которой инцидентны только входящие дуги.

96. Каков смысл уравнений сохранения потока?

Уравнение сохранения потока – это путь от источника к стоку, в котором для прямых дуг xij<yij, для обратных xij<0

97. Что такое аугментальная цепь?

Аугментальная цепь потока из s в t – связная последовательность прямых и обратных дуг, по которым из s в t можно послать несколько единиц потока.

98. Как можно увеличить поток, если имеется аугментальная цепь?

Аугментальная цепь используется для выбора такого способа изменения потока, при котором поток в узле увеличится и при этом для каждого внутреннего узла цепи не будет нарушено условие сохранения потока.

Пусть (i,j) ориентированная дуга из i в j. Поток по данной дуге может быть увеличен на qj единиц, если дуга (i,j) является прямой и узлу j приписываеся пометка +qj, i. Величина qj не может превосходить остат. Пропускные способности ui,j – fii.

Т.е. поток по прямой дуге (i,j) можно увеличить на величину qj, где qj = min (qj, ui,j – fii)