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

   ти (путь ‘назад’ бесперспективен). Для первого подграфа (рис.5.2б) кайма
   относительно b суть [e,d], для второго (рис.5.2в) - [d,f] (вершина а входит
   в обе каймы, но по указанным причинам исключается из рассмотрения).
   Имеем R(a,b,e)=7, R(a,b,d)=5, R(a,c,d)=8, R(a,c,f)=13. Заметим, что к вер-
   шине d от a ведут два ребра (через вершины b и c)!
4. Определить минимум из этих расстояний – наименьшее суть R(a,b,d)=5,
   что и позволяет принять в качестве частичного минимального пути [a,b,d].
   В случае двух или более одинаковых значений можно взять любое (обыч-
   но берется первое).
5. К списку вершин кратчайшего пути добавить только что определенные
   вершины b,d.
6. Повторять пункты 2 ÷ 5 алгоритма, принимая в качестве исходной послед-
   нюю из списка вершин частичного кратчайшего пути (в рассмотренном
   случае это вершина d) до тех пор, пока не будут проанализированы все
   входящие в вершину n ребра
   (для графа на рис.5.1 их 3).

   Т.о. при каждой итерации про-
двигаемся к конечной вершине на
две вершины (на два ребра), каж-
дый раз выбирая минимум пути
на протяжении смежных ребер.
После получения списка вершин
кратчайшего пути его длина оп-
ределяется примитивным сумми-
рованием метрик ребер (напр.,
для     графа    риc.5.1    имеем
  min
R (a,b,d,g,h,n)=12.
   Пользовательский интерфейс
программы OSPF приведен на
рис.5.3. В окне ввода описания
графа каждое ребро задается
строкой, где первые два слова –
имена определяющих ребро вер-
шин (длина имени не более 10
символов), далее - метрика ребра
(целое число); данные разделяют-
ся пробелами. Т.к. все ребра яв-
ляются ненаправленными, поря-
док указания определяющих их Рисунок 5.2 — К описанию алгоритма Дейк-
вершин несущественен. Главное         стры нахождения минимального пути в
меню является стандартным, вы-        графе.
числения начинаются выбором
варианта ‘Calculate’, проект и результаты расчета могут быть сохранены в

                                       39