Краткие теоретические сведения. Наикратчайшим путем между двумя узлами называют самый лучший или оптимальный путь, который можно использовать для передачи информации между ними

Наикратчайшим путем между двумя узлами называют самый лучший или оптимальный путь, который можно использовать для передачи информации между ними. Что в действительности называть наикратчайшим путем, зависит от критериев, привлекаемых для его оценки. Для такой оценки используются следующие параметры: число связей (звеньев), расстояние, задержку, битовую скорость передачи и стоимость.

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

Следующим шагом, учитывающим взвешенность звеньев, является поиск оптимального или наикратчайшего пути. В простых сетях его можно найти с помощью обычного обследования сети. Для сложных сетей необходимо опираться на формальные методы, и есть множество алгоритмов, разработанных специально для выполнения такой задачи. Алгоритмы Белмана-Форда и Дейкстры берут одиночный узел и вычисляют наикратчайшие пути между этим узлом и всеми другими узлами сети.

 

Алгоритм Дейкстры

Данный алгоритм находит самый короткий путь от данного узла до всех других узлов, работает следующим образом.

1. Маркируйте все узлы, кроме стартового, парой значений, состоящей из расстояния до данного узла (первоначально «») и именем узла подхода (первоначально «-»). Узел подхода – это ближайший (слева) соседний узел, к которому осуществляется непосредственный подход через маркируемый узел.

2. Начиная со стартового узла, выберите узел с самым низким совокупным весом; считайте этот узел установленным (или фиксированным).

3. Маркируйте соседние с установленным узлы совокупным расстоянием от стартового узла и именем узла подхода.

4. Если узел уже маркирован, то его метка заменяется на новую, совокупное расстояние которой меньше, чем существующее совокупное расстояние.

5. Продолжайте маркировку, пока все узлы не будут установлены.

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

1.

Каждый узел кроме стартового первоначально маркируется как .

Рис. 16 Пример применения алгоритма Дейкстры, шаг первый

 

2.

Начните с узла A, зафиксируйте его, перемаркируйте соседние (справа) узлы B и F с учетом их расстояний.

Рис. 17 Пример применения алгоритма Дейкстры, шаг второй

3.

Теперь самым малым весом обладает узел B, поэтому для него повторяются все действия пункта 2.

Рис. 18 Пример применения алгоритма Дейкстры, шаг третий

 

4. Теперь узел G имеет самый малый вес, поэтому он и используется. Новый вес для F меньше чем существующий, поэтому старая метка (6,A) заменяется новой (5,G). То же самое происходит и с узлом C.

Рис. 19 Пример применения алгоритма Дейкстры, шаг четвертый

 

5.

Повторите предыдущую процедуру для узла F. В результате узел E должен был бы получить метку (9, F), но его существующая метка (6,G) имеет более низкий суммарный вес до исходного узла, так что оставлена без изменений.

Рис. 20 Пример применения алгоритма Дейкстры, шаг пятый

 

6.

Повторите процедуру для узла C.

Рис. 21 Пример применения алгоритма Дейкстры, шаг шестой

 

7. Повторите процедуру для узла E. В результате метка узла D (9,C) будет заменена на (8,E).

 

Рис. 22 Пример применения алгоритма Дейкстры, шаг седьмой

 

Установка узла D завершает процедуру алгоритма Дейкстры. Нетрудно видеть, что самый короткий путь от A до D имеет совокупный вес 8, и читая метки, начинающиеся с узда D, в обратном порядке, получаем наикратчайший маршрут: D E G B A.