Математическая формулировка задачи, обоснование

2. Математическая формулировка задачи, обоснование

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

Покажем сначала основную идею метода Флойда. Пусть есть три узла i, j и k и заданы расстояния между ними (рис. 3). Если выполняется неравенство d_ij+ d_jk < d_ik, то целесообразно заменить путь i → k путем i → j → k. Такая замена (далее ее будем условно называть треугольным оператором) выполняется систематически в процессе выполнения алгоритма Флойда.

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

Шаг 0. Определяем начальную матрицу расстояний D₀ и матрицу последовательности

узлов S₀. Диагональные элементы обеих матриц помечаются знаком “ – “,

показывающим, что эти элементы в вычислениях не участвуют. Полагаем k=1.

Основной шаг. Задаем строку k и столбец k как ведущую строку и ведущий столбец.

Рассматриваем возможность применения треугольного оператора ко всем элементам d_ijматрицы D_k-1. Если выполняется неравенство

d_ij+ d_jk < d_ik (i ≠k, j≠k, i ≠j),

тогда выполняем следующие действия :

создаем матрицу D_k путем замены в матрице D_k-1 элемента d_ij на сумму d_ij+ d_jk, (рис. 4)

создаем матрицу S_k путем замены в матрице S_k-1 элемента s_ij на k. Полагаем k=k+1 и повторяют шаг k. (рис. 5)

рис. 4

рис. 5

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

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

Промежуточные узлы пути от узла i до узла j определяем по матрице S_n. Пусть s_ij = k, тогда имеем путь i → j → k. Если далее s_ik = k и s_ki = j, тогда считаем, что весь путь определен, так как найдены все промежуточные узлы. В противном случае повторяем описанную процедуру для путей от узла i к узлу k и от узла k к узлу j.

Похожие работы

VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования

Скачать

723413

0

0

... данных будет нести больше смысла, если его отсортировать каким‑либо образом. Часто требуется сортировать данные несколькими различными способами. Во‑вторых, многие алгоритмы сортировки являются интересными примерами программирования. Они демонстрируют важные методы, такие как частичное упорядочение, рекурсия, слияние списков и хранение двоичных деревьев в массиве. Наконец, сортировка ...

Организация интеллектуальной сети в г. Кокшетау на базе платформы оборудования Alcatel S12

Скачать

260457

20

40

... сети телекоммуникаций, а также сравнивая технические возможности оборудований различных фирм в настоящем дипломном проекте предлагаю создать интеллектуальную сеть в г.Кокшетау на базе оборудования S-12 фирмы Alcatel [6]. Выбор оборудования не случаен, так как на сети города полностью эксплуатируется данная система. Это позволяет оптимально решить вопросы по синхронизации, сигнализации и по ...

Применение методов дискретной математики в экономике

Скачать

34329

6

25

элементы теории нечетких множеств можно применять для решения экономических задач в условиях неопределённости. 1. применение Логических функций   1.1 Применение методов дискретной математики в экономике   При исследовании, анализе и решении управленческих проблем, моделировании объектов исследования и анализа широко используются методы формализированного представления, являющегося предметом ...

Организация международных грузовых автомобильных перевозок

Скачать

95433

0

2

... реализуется тем лучше, чем четче будет организовано выполнение всех работ по подготовке и обеспечению перевозочного процесса. Однако организация автомобильных перевозок грузов из одной страны в другую - процесс сложный, требующий соблюдения международных конвенций и соглашений по перевозкам и транзиту, высокого качества обслуживания, точного исполнения условий контракта, соблюдения таможенных и ...