Сети ЭВМ и телекоммуникации. Баканов В.М. - 38 стр.

Форда и применяется в основном на нижних уровнях иерархии сети. OSPF
применяет итерационный алгоритм Дейкстры для поиска кратчайшего пути
в графе и более эффективен при использовании в больших сетях (однако в
каждом маршрутизаторе должна иметься информация о состоянии всей се-
ти).
     Компьютерная сеть моделируется графом, причем вершины оного соот-
ветствуют маршрутизаторам, а ребра – каналам связи; вес ребер суть оценка
                                                      метрики (напр., рас-
                                                      стояния; причем мет-
                                                      рика неотрицательна)
                                                      между      инциндент-
                                                      ными - принадлежа-
                                                      щими        заданному
                                                      ребру -         узлами
                                                      (рис.5.1). Такой граф
                                                      является взвешенным
                                                      (т.к. каждому ребру
                                                      поставлено в соот-
                                                      ветствие некоторое
                                                      число), неориенти-
    Рисунок 5.1 — Сеть для примера маршрутизации [3].
                                                      рованным      (направ-
                                                      ленность ребер не-
существенна), не имеет петель (ребер, соединяющих вершину саму с собой)
и связным (из любой вершины можно найти путь в любую другую).
     Алгоритм Дейкстры поиска кратчайшего пути между двумя заданными
вершинами графа (*) является типичным примером поиска в ширину в графе
(‘жадный’ алгоритм) и фактически основан на выделении и анализе подгра-
фов в исходном графе. На рис.5.2 приведена схема алгоритма Дейкстры
применительно к первому шагу поиска кратчайшего пути в графе рис.5.1.
     Рассмотрим работу алгоритма для случая поиска кратчайшего пути между
вершинами а и n. Через R(i,j,k…) будем обозначать длину пути по вершинам
i,j,k…. Рассматриваемый алгоритм описан подробно в применении к перво-
му шагу поиска кратчайшего пути в графе рис.5.1 (в кайму относительно за-
данной вершины входят все вершины, отстоящие от нее на одно ребро):

1. Занести в список вершин кратчайшего пути начальную точку a.
2. Проанализировать число ребер, ведущих от начальной точки (в данном
   случае их два, см. рис.5.2a), в соответствие с этим разбить исходный граф
   на 2 подграфа (рис.5.2б и 5.2в).
3. Для каждого подграфа анализировать вершины, составляющие кайму
   (border) относительно a (это вершины [b,c]); при этом из рассмотрения
   исключаются вершины, уже входящие в список вершин кратчайшего пу-

*
    Д.Дж.Макконнелл. Анализ алгоритмов. –М.: Техносфера, 2002. -304 c.
                                            38