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

  • 12 нояб. 2014 г.
  • 425 Слова
Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования
Уфимский государственный авиационный технический университетОтчёт по лабораторной работе №2
«Кратчайшие узлы между всеми парами узлов.»











Выполнила:
студентка xxx

Проверил:
xxx






УФА, 2014
Цель работы: изучить алгоритм стройственными операциями для поиска кратчайшего пути между всеми парами узлов в сети.
Задача: реализовать алгоритм для поиска кратчайшего пути между всеми парами узлов в сети.
Краткая теоретическаячасть: Пусть , , , …,, - кратчайший путь из Vi в Vq. Тогда кратчайший путь из Vi в Vj должен представлять собой единственную дугу еij , кратчайший путь из Vj в Vk — дугу ejk, и т. д.
Длинакаждой построенной дуги равна кратчайшему расстоянию между двумя узлами. Для данного узла Vj рассмотрим следующую простую операцию:
(1)
Операция выполняется для каждого фиксированного j и всевозможных iи k, не равных j. Для трех узлов Vj, Vj и Vk и трех дуг с длинами dik , dij и djk данная операция сравнивает длину дуги еik , с длиной пути, состоящего из двух дуг, с промежуточным узлом Vj. Операция(1) называется тройственной операцией.
Для всевозможных пар узлов Vi и Vk, смежных с Vj , выполним следующие операции:
- если dik dij + djk, то никаких действий не производим;
- если dik > dij +djk,, то создаем новую дугу, ведущую из Vi в Vk с dik = dij + djk .
Схема алгоритма:
1) Фиксируем j = 1 и выполняем тройственную операцию (1) для всех i, k = 2, 3,..., n.
2) Фиксируем j = 2 ивыполняем тройственную операцию (1) для всех i, k = 1, 3,..., n.
Замечание. Все новые дуги, добавленные при j = 1, используются далее при j = 2, и т.д.
Кратчайшие расстояния между каждой парой узловнайдены. Но необходимо найти промежуточные (внутренние) узлы для кратчайших путей.
Чтобы зафиксировать порядок, в котором появляются эти узлы, мы используем матрицу [pi,k], в которой...