![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
В разд. 6.1 были рассмотрены алгоритмы нахождения кратчайших путей в графе из начальной вершины до конечной вершины или до всех других вершин (алгоритмы Дейкстры и Форда). Теперь рассмотрим задачу поиска кратчайших путей между каждой парой вершин. Решить её можно, применив рассмотренные в разд. 6.1 алгоритмы для каждой вершины, то есть в качестве начальной брать по очереди все вершины графа и находить кратчайшие пути из начальной вершины до всех других вершин. Такой подход для графа G =(V, E) с неотрицательными весами дуг дал бы алгоритм с трудоемкостью О(| V |3). В случае графов с отрицательными весами дуг трудоемкость резко возрастает. Однако для нахождения кратчайших путей между каждой парой вершин существует более общий метод (алгоритм Флойда), требующий О(| V |3) операций даже для графов с отрицательными весами дуг.
Пусть W =║ wij ║- матрица весов графа G =(V, E), и мы хотим вычислить матрицу W *=║ wij *║, в которой wij * - длина кратчайшего пути из i Î V в j Î V.
Аналогично методу вычисления транзитивного замыкания (разд. 5.4) можно вычислить матрицу W *, определив последовательность матриц W (0)=║ wij (0)║, W (1)=║ wij (1)║,¼, W (|V|)=║ wij (|V|)║, следующим образом:
1) wij (0)= wij;
2) wij ( k )=min{ wij ( k -1), wik ( k -1)+ wkj ( k -1)}. (6.2)
Утверждение: Значение wij ( k ) есть длина кратчайшего пути из вершины i Î V в вершину j Î V с промежуточными вершинами, принадлежащими множеству {1,2,¼, k }Í V. Тогда W (| V |) – матрица кратчайших путей, а элемент матрицы wij равен длине кратчайшего пути из вершины i в вершину j.
Доказательство данного утверждения проводится методом математической индукции, аналогично доказательству утверждения в разд.5.4.
Алгоритм 4.Алгоритм Флойда
Алгоритм следует из выражения 6.2
for k = 1 to | V | do
for i = 1 to | V | do
for j = 1 to | V | do
wij min{ wij, wik + wkj }
Заметим, что на алгоритм отрицательность весов не влияет, но если в графе имеется контур отрицательной длины, то алгоритм не работает. Также отметим, что данный алгоритм является более эффективным для вычисления единственного кратчайшего пути в плотном орграфе, чем алгоритм Форда.
Упражнения:
1. Как и при реализации алгоритма нахождения транзитивного замыкания (алгоритм 2, разд.5.4), в алгоритме 4 элементы (k -1)-ой матрицы непосредственно преобразуются в элементы матрицы k -ой матрицы. Докажите корректность такой реализации.
2. Алгоритм 4 вычисляет только длины кратчайших путей между каждой парой вершин. Доработайте алгоритм таким образом, чтобы сохранялась информация о самих кратчайших путях (см. разд.5.4, упр.4).
ПОТОКИ
Поток определяет способ пересылки некоторых объектов из одного пункта в другой. Потоки, например, возникают при транспортировке товаров, при движении людей и транспорта и так далее.
Применительно к графам поток задает способ пересылки некоторых объектов (единиц потока) из одной вершины графа (из источника) в другую вершину (сток) по дугам в направлении их ориентации. Максимальное число единиц потока, которые могут проходить по дуге, называют пропускной способностью дуги. Кроме пропускной способности дуг в некоторых задачах задают стоимость прохождения единицы потока по дугам.
В данной главе будут рассмотрены алгоритмы поиска максимального потока и поиска потока минимальной стоимости. Также в данной главе рассматриваются подходы к решению задач 1 и 2, сформулированных во введении к данному пособию.
Дата публикования: 2015-01-04; Прочитано: 387 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!