Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Математика / Графы. Поиск маршрутов / Задача о кратчайших путях /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Алгоритм Флойда - Программирование от RIN.RU
Алгоритм Флойда

Дано: непyстой взвешенный гpаф G=(V, E) с пpоизвольными весами ребер (дуг). Требуется найти длины кpатчайших пyтей между всеми парами вершин графа, если в графе нет циклов (контуров) отрицательной суммарной длины, либо обнаружить наличие таких контуров.


Инициализация:


1. Построим матрицу D0 размерности |V| x |V|, элементы которой определяются по правилу:


  1. dii0= 0;


  2. dij0= Weight(vi, vj), где i<>j, если в графе существует ребро (дуга) (vi, vj);


  3. dij0= бесконечность , где i<>j, если нет ребра (дуги) (vi, vj).



2. m:=0.
Основная часть:
1. Построим матрицу Dm+1 по Dm, вычисляя ее элементы следующим образом:


dijm+1=min{dijm, di(m+1)m + d(m+1)jm}, где i<>j; diim+1=0 (*).


Если dimm + dmim < 0 для какого-то i, то в графе существует цикл (контур) отрицательной длины, проходящий через вершину vi; ВЫХОД.


2. m:=m+1; если m<|V|, то повторяем шаг (1), иначе элементы последней построенной матрицы D|V| равны длинам кратчайших путей между соответствующими вершинами; ВЫХОД.


КОНЕЦ


Если требует найти сами пути, то перед началом работы алгоритма построим матрицу P с начальными значениями элементов pij=i. Каждый раз, когда на шаге (1) значение dijm+1 будет уменьшаться в соответствии с (*) (т.е. когда di(m+1)m + d(m+1)jm<dijm),
выполним присваивание pij:=p(m+1)j. В конце работы алгоритма матрица P будет определять кратчайшие пути
между всеми парами вершин: значение pij будет равно номеру предпоследней вершины в пути между i и j (либо pij=i, если путь не существует).


Примечаниe: если граф - неориентированный, то все матрицы Dm являются симметричными, поэтому достаточно вычислять элементы, находящиеся только выше (либо только ниже) главной диагонали.



 8  Комментарии к статье  8  Обсудить в форуме  8  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь
Данный сайт предоставляет информацию.