Нахождение кратчайшего пути в графе

  • 14 июня 2014 г.
  • 901 Слова
Нахождение кратчайшего пути в графе
Пусть дан граф, дугам которого приписаны веса. Задача о нахождении кратчайшего пути состоит в нахождении кратчайшего пути от заданной начальной вершины дозаданной конечной вершины, при условии, что такой путь существует.
Можно дать много практических интерпретаций задачи о кратчайших путях. Например, вершины могут соответствовать городам и каждая дуга -некоторому пути, длина которого представлена весом дуги. Мы ищем кратчайшие пути между городами. Вес дуги может соответствовать стоимости (или времени) передачи информации между вершинами. В этом случае мы ищем самыйдешевый (или самый скорый).
Данная задача может быть разбита на две:
1. для начальной заданной вершины найти все кратчайшие пути от этой вершины к другим;
2. найти кратчайшие пути между всемипарами вершин.
Рассмотрим алгоритм решения для задачи первого типа:
Необходимо найти путь от s - начальной вершины до t - конечной вершины. Каждой вершине присваиваем пометки I(Xi).
1. I(s) = 0,I(Xi) равно бесконечности для всех Хi не равных s и считать эти пометки временными. Положить р = s.
2. Для всех Хi, пренадлежащих Г(р) и пометки которых временны, изменить пометки по следующемуправилу:
I(Xi) = min[I(Xi), I(p) + c(p, Xi)]
3. среди всех вершин с временными пометками найти такую, для которой I(Xi*) = min[I(Xi)]
4. считать пометку вешины Хi* постоянной и положить р =Хi*.
5. если р = t, то I(р) является длинной кратчайшего пути, если нет, перейти к шагу 2.
Как только все пометки расставлены, кратчайшие пути получают, используя состношение I(Xi') + c(Xi',Xi) =I(Xi).

Алгоритм Форда-Фалкерсона
Алгоритм Форда-Фалкерсона — решает задачу нахождения максимального потока в транспортной сети.
Задача о максимальном потоке для данной сети состоит в следующем:найти максимально возможную скорость производства (и потребления) вещества, при которой его еще можно доставить от истока к стоку при данных пропускных способностях труб....