Читайте также:
|
Постановка задачи:
Пусть задан орграф G=(V,E) с заданными положительными длинами ребер. Найти длину кратчайшего пути (и сам путь), соединяющий 2 произвольные фиксированные вершины s (начало) и t (конец).
Алгоритм Дейкстры:
1. В начале алгоритма все вершины не окрашены. Каждой вершине V во время выполнения алгоритма ставиться в соответствие либо L(V) – длина кратчайшего пути включающего только окрашенные вершины, L'(V) – временная метка, которая становиться равной L(V) в момент когда V окрашивается.
Полагаем что L(S)=0, L’(V)=∞, S≠V. Окрашиваем вершину S.
2. Для каждой неокрашенной вершины и соседней с последней из окрашенных вершинV пересчитываем L(U)=min{L’(U), L(V)+L(V,U)}, где L(V,U) – длина дуги между V и U.
Если L'(U)=∞ для любой неокрашенной вершины U, то алгоритм следует закончить. Так как в исходной сети не существует пути из S в неокрашенные вершины, в том числе и в Е. в противном случае находим вершины R, для которой L'(R) =L’(U), после чего К окрашиваем и вносим в корневое дерево дугу (V,R). Вершина R становится последней из окрашенных вершин.
3. В момент, когда вершина T становится окрашенной, находим кратчайший путь, соединяющий S и T, состоящий из окрашенных дуг.
Алгоритм Басакера-Гоуэна (назначение, постановка задачи)
Задана сеть, каждой дуге которой поставлено в соответствие 3 числа: с(х,у) – пропускная способность дуги, f(x,y) – поток по дуге, d(x,y) - стоимость провода единицы потока по дуге x,y. Требуется пропустить в сети поток заданной величины V или максимальный поток минимальной стоимости.
Дата добавления: 2015-04-20; просмотров: 266 | Поможем написать вашу работу | Нарушение авторских прав |