Разделы

Алгоритм Флойда

Этот алгоритм более общий по сравнению с алгоритмом Дейкстры, так как он находит кратчайшие пути между любыми двумя узлами сети. В этом алгоритме сеть представлена в виде квадратной матрицы с n строками и n столбцами. Элемент (i, j) равен расстоянию dij от узла i к узлу j, которое имеет конечное значение, если существует дуга (i, j), и равен бесконечности в противном случае.

Покажем сначала основную идею метода Флойда. Пусть есть три узла i, j и k и заданы расстояния между ними (рис.2.1). Если выполняется неравенство dij + djk < dik, то целесообразно заменить путь i -> k путем i -> j -> k. Такая замена (далее ее будем условно называть треугольным оператором) выполняется систематически в процессе выполнения алгоритма Флойда.

Рис.2.1. Треугольный оператор

Алгоритм Флойда требует выполнения следующих действий.

Шаг 0. Определяем начальную матрицу расстояния D0 и матрицу последовательности узлов S0. Диагональные элементы обеих матриц помечаются знаком "-", показывающим, что эти элементы в вычислениях не участвуют. Полагаем k = 1:

Рис.2.2 Начальная ситуация

Основной шаг k. Задаем строку k и столбец k как ведущую строку и ведущий столбец. Рассматриваем возможность применения треугольного оператора ко всем элементам dij матрицы Dk-1. Если выполняется неравенство dik + dkj < dij, (i <> k, j <> k, i <> j), тогда выполняем следующие действия:

· создаем матрицу Dk путем замены в матрице Dk-1 элемента dij на сумму dik + dkj,

· создаем матрицу Sk путем замены в матрице Sk-1 элемента sij на k. Полагаем k = k + 1 и повторяем шаг k.

Поясним действия, выполняемые на k-м шаге алгоритма, представив матрицу Dk-1 так, как она показана на рисунке 2.3. На этом рисунке строка k и столбец k являются ведущими. Строка i - любая строка с номером от 1 до k - 1, а строка p - произвольная строка с номером от k + 1 до n. Аналогично столбец j представляет любой столбец с номером от 1 до k - 1, столбец q - произвольный столбец с номером от k + 1 до n. Треугольный оператор выполняется следующим образом. Если сумма элементов ведущих строки и столбца (показанных в квадратах) меньше элементов, находящихся в пересечении столбца и строки (показанных в кружках), соответствующих рассматриваемым ведущим элементам, то расстояние (элемент в кружке) заменяется на сумму расстояний, представленных ведущими элементами:

Рис 2.3. Иллюстрация алгоритма Флойда

После реализации n шагов алгоритма определение по матрицам Dn и Sn кратчайшего пути между узлами i и j выполняется по следующим правилам.

1. Расстояние между узлами i и j равно элементу dij в матрице Dn.

2. Промежуточные узлы пути от узла i к узлу j определяем по матрице Sn. Пусть sij = k, тогда имеем путь i -> k -> j. Если далее sik = k и skj = j, тогда считаем, что весь путь определен, так как найдены все промежуточные узлы. В противном случае повторяем описанную процедуру для путей от узла i к узлу k и от узла k к узлу j.

.2 Описание интерфейса и работы программы

Рис.2.4. Интерфейс программы

По описанному выше алгоритму была разработана и написана программа.

В левой части окна располагаются матрица расстояний и матрица последовательности узлов. Кнопка "Рассчитать". Справа расположены: поле графа, где выставляются вершины графа, выбор режима соединения вершин графа, поля ввода ввершин для нахождения кратчайшего расстояния между ними, кнопка , по нажатию которой вычисляется это расстояние.

Порядок работы с программой:

) Выставить вершины на поле графа. Вершины выставляются щелчком левой кнопки мыши.

) Выбрать режим соединения вершин. Соединить вершины между собой. Граф должен быть связным, т.е. граф, в котором все вершины связаны.

) Нажать кнопку "Рассчитать". После этого произойдет оптимизация матрицы расстояний и последовательности узлов по алгоритму Флойда.

) Ввести номер 1 и 2 вершины, по нажатию кнопки "Найти кратчайшее расстояние" оно будет рассчитано.

Рис.2.5 Построение графа.Вычисление кратчайшего расстояния.

Другие материалы

Проектирование цифрового счетчика
Счетчиком называется последовательное устройство, предназначенное для счета входных импульсов и фиксации их числа в двоичном коде. Счетчики так же, как и сдвиговые регистры, строятся на ...

Разработка декодера инверсного кода
В настоящее время широкое применение нашли цифровые телемеханические системы, в которых измеряемая величина передается в виде определенной кодовой комбинации. Цифровые методы передачи ин ...

Расчет элементов блоков радиоэлектронной аппаратуры
Курсовая работа по учебной дисциплине "Эксплуатация АСУ" предназначены для закрепления лекционного материала и привития студентам практических навыков в решении ...

Копирайт 2019 : www.ordinarytech.ru