Программирование и комп-ры

Aлгоритмы на графах

Элементы теории графов.
 Граф - совокупность точек и линий, в которой каждая  линия  соединяет  две
точки. Точки называются  вершинами,  или  узлами,  графа,  линии  -  ребрами
графа. Если ребро соединят две вершины, то говорят, что оно  им  инцидентно;
вершины, соединенные ребром называются смежными.  Две вершины,   соединенные
ребром,  могут совпадать;  такое  ребро  называется  петлей.   Число  ребер,
инцидентных  вершине,  называется  степенью   вершины.   Если    два   ребра
инцидентны одной и той же паре вершин,   они  называются   кратными;   граф,
содержащий кратные ребра, называется мультиграфом.
 Ребро, соединяющее две вершины,  может иметь направление от одной  вершины
к другой;  в этом случае оно называется направленным,  или  ориентированным,
и  изображается  стрелкой.  Граф,  в  котором  все  ребра   ориентированные,
называется ориентированным графом (орграфом); ребра орграфа  часто  называют
дугами. Дуги именуются кратными, если  они  не  только имеют общие  вершины,
 но и совпадают по направлению. Иногда нужно рассматривать не весь  граф,  а
его часть (часть вершин и часть ребер). Часть вершин и  все  инцидентные  им
ребра называются  подграфом;  все  вершины  и  часть  инцидентных  им  ребер
называются  суграфом.  Циклом  называется  замкнутая  цепь  вершин.  Деревом
называется граф без циклов. Остовным  деревом  называется  связанный  суграф
графа, не имеющий циклов.
   Граф однозначно задан,  если заданы  множество  его  вершин,   множество
ребер и указаны все  инцидентности  (т.е.  указано,   какие  вершины  какими
ребрами соединены). Наиболее наглядно граф  задается  рисунком;   однако  не
все  детали   рисунка   одинаково   важны;    в   частности,   несущественны
геометрические   свойства  ребер  (длинна,  кривизна  и  т.д.)  и   взаимное
расположение вершин на плоскости.
   Для неориентированного ребра порядок, в котором указанны соединяемые  им
вершины,  не важен.  Для ориентированного  ребра  важно: первой  указывается
вершина, из которой выходит ребро.
   Маршрут, или путь - это  последовательность  ребер  в  неориентированном
графе,  в  котором  конец  каждого  ребра  совпадает  с  началом  следующего
ребра. Число ребер маршрута называется его длинной.
   Графы широко   используются   как  в  самой  математике,   так  и  в  ее
приложениях.  Они  применяются  при  построении   различных   математических
моделей: линий электропередачи, сетей автодорог, линий  воздушных  сообщений
и пр.
   Задача состоит в том,  найти путь  из  вершины  A  в  вершину  B.  Будем
задавать граф  матрицей  смежности,   т.е.   квадратной   таблицей  NxN,   в
которой на пересечении i-й строки и j-го столбца значение TRUE, если i  и  j
соединены ребром, и FALSE в противном случае.



                               Поиск в ширину.
   Подобно тому как, согласно принципу  Гюйгенса,  каждая  точка  волнового
фронта является источником вторичной волны,   мы,  отправляясь  из  заданной
вершины A,  посещаем все смежные  с  ней  вершины (т.е. вершины,  в  которые
ведут стрелки из A).  Каждая посещенная вершина становится источником  новой
волны и т.д. При этом необходимо позаботиться о том,  чтобы  не  вернутся  в
ту вершину, в которой уже были.
   Для реализации алгоритма понадобятся:
   матрица m[1..n, 1..n] - матрица смежности графа;
   вспомогательный массив  queue[1..n],   в   котором  будет  формироваться
очередь, т.е. тип данных первый вошел –  первый  вышел  (FIFO).  Размер  его
достаточен,  так как  мы  не  посещаем  вершины  дважды.  С  массивом  queue
связаны две переменные - head и tail. В  переменной  head  будет  находиться
номер текущей вершины,  из которой идет  волна,  а  при  помощи   переменной
tail  новые  вершины  помещаются  в "хвост" очереди queue;
   вспомогательный массив visited[1..n],  который нужен  для   того,  чтобы
отмечать уже пройденные вершины (visited[i]=TRUE <=> вершина i пройдена);
   вспомогательный массив  prev[1..n] для  хранения  пройденных  вершин.  В
этом массиве и будет сформирован искомый путь;
   переменная f,  которая  примет значение TRUE,  когда путь будет найден.
   Кроме того, мы  введем  несколько  вспомогательных  переменных,  которые
понадобятся при организации циклов.
   Program breadth_first_search;
   Const n=9;
         m:array[1..n, 1..n] of boolean =
         (
            (False,  True,   True,   False,  False,  False,  False,  False,
False),
             (True,   False,  True,   False,  False,  False,  True,   True,
False),
            (True,   True,   False,  True,   True,   False,  False,  False,
False),
            (False,  False,  True,   False,  True,   False,  False,  False,
False),
             (False,  False,  True,   True,   False,  True,   False,  True,
False),
            (False, False, False, False, True,  False, True,   True,   True
),
            (False, True,  False, False, False, True,  False,  True,   True
),
            (False,  True,   False,  False,  True,   True,   True,   False,
False),
            (False, False, False, False, False, True,  True,  False, False)
         );
   Var A, B: integer;

    Procedure A_to_B(A, B: integer);
    Var
         Visited: array[1..n] of boolean;
            Prev: array[1..n] of integer;
            c: array[1..n] of integer;
      head, tail: integer;
               f: boolean;
         i, v, k: integer;
    Begin
      head:=1;
      tail:=1;
      f:=False;
      For i:=1 to n do
      Begin
        Visited[i]:=False;
        Prev[i]:=0
      End;
      C[tail]:=A;
      Visited[A]:=True;
      While (head<=tail) and not f do
      Begin
        v:=C[head];
        head:=head+1;
        For k:=1 to n do
          if m[v, k] and not Visited[k] then
                                        Begin
                                          tail:=tail+1;
                                          C[tail]:=k;
                                          Visited[k]:=True;
                                          Prev[k]:=v;
                                          if k=B then
                                                 Begin
                                                   f:=true;
                                                   break
                                                 End
                                        End
      End;
      if f then
           Begin
             k:=B;
             Write(B);
             While Prev[k]<>0 do
             Begin
               Write('<-', Prev[k]);
               k:=Prev[k]
             end
           End
           else
                Write('Пути из ', A, ' в ', B, ' нет')
    end;

   Begin
     Write('A= '); readln(A);
     Write('B= '); readln(B);
     A_to_B(A, B)
   End.



Поиск в глубину.
   Идея поиска в глубину проста: отправляясь от текущей вершины, мы находим
новую (еще не пройденную) смежную  с  ней  вершину,   которую  помечаем  как
пройденную и объявляем текущей.  После этого  процесс  возобновляется.  Если
новой смежной вершины нет (тупик), возвращаемся к той  вершине,  из  которой
попали в текущую, и делаем следующую попытку.  Если  попадем  в  вершину  B,
печатаем путь.  Если все вершины исчерпаны - такого пути нет.
   Заметим, что построенный таким образом алгоритм способен   находить  все
пути из A в B,  но первый найденный необязательно должен быть кратчайшим.
   Как обычно,  алгоритм  с  возвратами  легче  всего  оформить  с  помощью
рекурсивной процедуры. Для ее реализации нам понадобятся:
   матрица m[1..n, 1..n] - матрица смежности графа;
   вспомогательный массив visited[1..n],  который мы будем для того,  чтобы
отмечать  уже  пройденные вершины (visited[i]=TRUE <=> вершина i пройдена);
   переменная f,  которая  примет значение TRUE,  когда путь будет найден.

   Program depth_first_search;
   Const n=9;
         m:array[1..n, 1..n] of boolean =
         (
            (False,  True,   True,   False,  False,  False,  False,  False,
False),
             (True,   False,  True,   False,  False,  False,  True,   True,
False),
            (True,   True,   False,  True,   True,   False,  False,  False,
False),
            (False,  False,  True,   False,  True,   False,  False,  False,
False),
             (False,  False,  True,   True,   False,  True,   False,  True,
False),
            (False, False, False, False, True,  False, True,   True,   True
),
            (False, True,  False, False, False, True,  False,  True,   True
),
            (False,  True,   False,  False,  True,   True,   True,   False,
False),
            (False, False, False, False, False, True,  True,  False, False)
         );
   Var A, B: integer;

    Procedure A_to_b(A, B: integer);
    Var
       Visited: array[1..n] of boolean;
              f: boolean;
              i: integer;

     Procedure Depth(p: integer);
     var k: integer;
     Begin
       Visited[p]:=True;
       For k:=1 to n do
         If not f then
           If m[p, k] and not Visited[k] then
             If k=B then
                    Begin
                      f:=True;
                      Write(B);
                      Break
                    End
                    else Depth(k);
       If f then write('<=', p);
     End;

    Begin
      For i:=1 to n do Visited[i]:=False;
      f:=false;
      Depth(A);
      If not f then write('Пути из ', A, ' в ', B, ' нет')
    End;


   Begin
     write('A= '); readln(A);
     write('B= '); readln(B);
     A_to_B(A, B)
   End.



Эйлеровы циклы.
   Требуется найти цикл, проходящий по каждой  дуге  ровно  один  раз.  Эту
задачу впервые поставил и   решил   Леонард  Эйлер,  чем  и  заложил  основы
теории графов, а соответствующие циклы теперь называются эйлеровыми.
   Задача возникла из предложенной Эйлеру головоломки,  получившей название
"проблема  кенигсбергских  мостов".  Река  Прегель,   протека   ющая   через
Калининград  (прежде  город  назывался Кенигсбергом), омывает  два  острова.
Берега реки связаны с островами  так,  как  это  показано  на   рисунке.   В
головоломке  требовалось найти маршрут, проходящий  по  всем  участкам  суши
таким образом,  чтобы каждый  из мостов  был  пройден  ровно  один  раз,   а
начальный и конечный пункты маршрута совпадали.


 Выберем в качестве вершин графа берега реки, а в качестве  ребер -  мосты,
их  соединяющие.   После  этого  задача  становится  очевидной:   требование
неосуществимо -  чтобы  его  выполнить,   число  дуг,  приходящих  к  каждой
вершине, должно быть четным. В самом деле, поскольку по одному мосту  нельзя
 проходить  дважды,  каждому входу на берег должен соответствовать выход.
   Что необходимо, чтобы в графе существовал эйлеров цикл? Во-первых,  граф
должен быть связанным: для любых двух вершин должен  существовать  путь,  их
соединяющий. Во-вторых, для неориентированных графов число  ребер  в  каждой
вершине должно быть четным.  На самом деле этого оказывается достаточно.
 Теорема. Чтобы  в  связанном  графе   существовал эйлеров цикл, необходимо
и достаточно, чтобы число ребер в каждой вершине было четным.
 Доказательство.   Необходимость     доказана     выше.      Доказательство
достаточности  конструктивно   -  в  результате  будет   получен   требуемый
алгоритм.
    Доказательство  ведется   индукцией   по  числу  ребер  графа.    Пусть
утверждение доказано для всех mnil do
    Begin
      Write(l^.i:3);
      l:=l^.next
    End
  End;

 Begin
   stack1:=nil;
   stack2:=nil;
   Write('Начальная вершина: ');readln(v);
   Push(v, stack1);
   While stack1<>NIL do
   Begin
     v:=peek(stack1);
     i:=1;
     While (i<=n) and not m[v, i] do inc(i);
     If i<=n then
             Begin
               u:=i;
               Push(u, stack1);
               m[v, u]:=False;
               m[u, v]:=False;
             End
             else
             Begin
               pop(x, stack1);
               push(x, stack2)
             End
   End;
   PrintList(stack2)
 End.



                           Задача Прима–Краскала.
   Дана плоская страна и в  ней  n  городов.  Нужно  соединить  все  города
  телефонной  связью  так,  чтобы  общая  длинна  телефонных   линий   была
  минимальной.
 Или в терминах  теории графов:
   Дан граф с n вершинами; длины  ребер  заданы  матрицей.  Найти  остовное
  дерево минимальной длины.
 Представим себе, что зимовщику оставлен некоторый запас продуктов,  и  его
задачей является составление  вкусного  меню  на  всю  зиму.  Если  зимовщик
начнет с того, что сперва будет есть самую вкусную еду (например,  шоколад),
потом – вторую по вкусности (например, мясо),  то  он  рискует  оставить  на
последний месяц только соль и маргарин. Подобным образом,  если  оптимальный
(для определенности,  минимальный)  объект  строится  как-то  по  шагам,  то
нельзя на первом шаге выбирать что-нибудь самое  малое,  на  втором  шаге  –
оставшееся  самое  малое  и  т.д.  За  такую  политику   обычно   приходится
расплачиваться на последних шагах. Такой алгоритм называется жадным.
 Удивительно, но в  задаче  Прима–Краскала,  которая  не  кажется  особенно
простой, жадный алгоритм дает точное оптимальное решение.
 Как известно (это легко доказать по индукции), дерево с n вершинами  имеет
n-1 ребер. Оказывается, каждое  ребро  нужно  выбирать  жадно  (лишь  бы  не
возникали циклы). То есть n-1 раз выбирать самое короткое ребро  из  еще  не
выбранное ребро при условии, что оно не образует цикла с уже выбранными.
 А как следить, чтобы  новое  ребро  не  образовывало   цикла  со  старыми?
Сделать это  просто.  До  построения  дерева  окрасим  каждую  вершину  i  в
отличный от других цвет i. При выборе очередного  ребра,  например  (i,  j),
где i и j имеют разные цвета, вершина j и все, окрашенные в  ее  цвет  (т.е.
ранее с ней соединенные) перекрашиваются в  цвет  i.  Таким  образом,  выбор
вершин разного цвета обеспечивает отсутствие циклов. После выбора n-1  ребер
все вершины получают один цвет.
 Докажем, что описанный алгоритм получает в точности  минимальное  решение.
Для доказательства нам понадобится очень простое утверждение:
 Если к дереву добавить ребро, то в дереве появится  цикл,  содержащий  это
 ребро.
 Действительно, пусть добавлено ребро (u, v) –  “добавлено”  означает,  что
ребро – новое, что раньше его в дереве не было.  Поскольку  дерево  является
связанным графом, то существует  цепь   C(u,  …,  v)  из  нескольких  ребер,
соединяющая вершины u и v. Добавление ребра (u, v) замыкает цепь,  превращая
ее в цикл.
 Теорема. Алгоритм Прима–Краскала получает минимальное остовное дерево.
 Доказательство. Результатом работы алгоритма является набор из n-1  ребер.
Они не образуют цикла, ибо  на  каждом  из  n-1  шагов  соединялись  вершины
разного цвета, т.е. ранее не связанные. Этот граф связный, потому что  после
проведения  1-го ребра осталось n-1 разных цветов, …, после  проведения  (n-
1)-го ребра  остался  один  цвет,  т.е.  одна  компонента  связности.  Итак,
полученный набор ребер образует связный  граф  без  циклов,  содержащий  n-1
ребер и  n  вершин.  Следовательно,  граф  есть  остовное  дерево.  Осталось
доказать, что оно имеет минимальную длину. Пусть {[pic],  [pic],  …,  [pic]}
ребра  остовного  дерева  в  том  порядке  как  их  выбирал  алгоритм,  т.е.
[pic]([pic]. Предположим для простоты доказательства,  что  все  ребра  сети
имеют разную длину, т.е.
                                                        [pic]<[pic]<…<[pic]
                                     (1)
 Если  полученное  дерево  не  минимально,  то  существует  другое  дерево,
заданное набором из n-1 ребер {[pic], [pic],  …,  [pic]},  такое  что  сумма
длин [pic] меньше суммы длин [pic]. С точностью до обозначений
                                                        [pic]<[pic]<…<[pic]
                                  (2)
 Может быть [pic]=[pic], [pic]=[pic] и т.д., но так как деревья разные,  то
в последовательностях (1) и (2) найдется место, где ребра отличаются.  Пусть
самое  левое  такое  место  –  k,  так  что  [pic]([pic].  Поскольку   [pic]
выбиралось по алгоритму самым  малым   из  не  образующих  цикла  с  ребрами
[pic], [pic], …, [pic], то [pic]<[pic]. Теперь добавим к  дереву  (2)  ребро
[pic]; в нем появится цикл, содержащий ребро [pic] и, может  быть,  какие-то
(или все) ребра [pic], [pic], …, [pic],  но  они  сами  не  образуют  цикла,
поэтому в цикле будет обязательно ребро d из набора [pic], …, [pic],  причем
d>[pic]. Выбросим из полученного графа с одним  циклом  ребро  d;  мы  снова
получим  дерево,  но  оно  будет  на  d-[pic]   короче   минимального,   что
невозможно. Полученное противоречие доказывает теорему  для  сети  со  всеми
разными ребрами.
 Для реализации алгоритма понадобятся:
   Matrix – матрица расстояний, значение пересечении  i-ой  строки  и  j-го
столбца равно расстоянию между  i-ой и  j-ой вершинами.  Если  такого  ребра
нет  то  значение  равно  Infinity  –  просто   большому   числу   (машинная
бесконечность);
   Color – массив цветов вершин;
   Ribs – в этом массиве запоминаются найденные ребра;
   a, b – вершины, соединяемые очередным минимальным ребром
   len – длина дерева.
 Матрицу расстояний будем хранить в текстовом файле INPUT.MTR, где число на
первой строке – количество вершин n, а  остальные  n  строк  по  n  чисел  в
каждой – матрица расстояний.  Если  расстояние  равно  1000  (Infinity),  то
такого ребра нет.

Program Algorithm_PrimaKrascala;
Uses Crt;
Const MaxSize =100;
            Infinity =1000;
Var   Matrix: array[1..MaxSize, 1..MaxSize] of integer;
          Color: array[1..MaxSize] of integer;
            Ribs: array[1..MaxSize] of record
                                                        a, b: integer;
                                                      end;
   n, a, b, k, col, i, len: integer;

 Procedure Init;
 Var    f: text;
        i, j: integer;
 Begin
   Assign(f, 'INPUT.MTR');
   Reset(f);
   Readln(f, n);
   For i:=1 to n do
   Begin
     For j:=1 to n do read(f, matrix[i, j]);
     Readln(f)
   End;
   For i:=1 to n do color[i]:=i;
   len:=0
 End;

 Procedure Findmin(var a, b: integer);
 Var min, i, j: integer;
 Begin
   min:=infinity;
   For i:=1 to n-1 do
     For j:=i+1 to n do
      If (Matrix[i, j]color[j]) then
         Begin
           min:=Matrix[i, j];
           a:=i;
           b:=j
         End;
   len:=len+min
 end;

Begin
  Clrscr;
  Init;
  For k:=1 to n-1 do
  Begin
    Findmin(a, b);
    Ribs[k].a:=a;
    Ribs[k].b:=b;
    col:=Color[b];
    For i:=1 to n do
      If color[i]=col then color[i]:=color[a];
  End;
  For i:=1 to n-1 do
     Writeln(ribs[i].a, ' –', ribs[i].b);
  Writeln('Length= ', len);
  Readkey
End.
 Для такого входного файла
8
0        23      12     1000  1000  1000   1000  1000
23      0        25     1000  22      1000   1000  35
12      25      0       18      1000  1000   1000  1000
1000  1000  18      0       1000  20       1000  1000
1000  22      1000  1000  0       23       14      1000
1000  1000  1000  20      23     0         24      1000
1000  1000  1000  1000  14      24      0        16
1000  35      1000  1000  1000  1000  16      0
программа напечатает:
1–3
5–7
7–8
3–4
4–6
2–5
1–2
Length= 125.



                             Алгоритм Дейкстры.
  Дана дорожная сеть, где города и развилки будут  вершинами,  а  дороги  –
 ребрами. Требуется найти кратчайший путь между двумя вершинами.
 Можно предложить много процедур решения этой задачи, например,  физическое
моделирование такого рода: на плоской  доске  рисуется  карта  местности,  в
города и в развилки вбиваются гвозди, на каждый  гвоздь  надевается  кольцо,
дороги  укладываются  веревками,  которые  привязываются  к  соответствующим
кольцам. Чтобы найти кратчайшее расстояние между  кольцом  i  и  кольцом  k,
нужно взять i в одну руку,  взять  k  в  другую  и  растянуть.  Те  веревки,
которые натянутся и не дадут разводить  шире,  и  образуют  кратчайший  путь
между i и k. Однако, математическая  процедура,  которая  промоделирует  эту
физическую, выглядит очень сложно.  Известны  алгоритмы  попроще,  например,
предложенный Дейкстрой еще в  1959  г.  Этот  алгоритм  решает  более  общую
задачу:
  В ориентированной, неориентированной или смешанной сети найти  кратчайший
 путь из заданной вершины во все остальные вершины.
 Алгоритм использует три массива  из n чисел каждый. Первый массив  Visited
содержит метки с двумя значениями: False  (вершина  еще  не  рассмотрена)  и
True (вершина уже рассмотрена); второй массив Len содержит расстояния  от  –
текущие кратчайшие  расстояния  от  начальной  до  соответствующей  вершины;
третий массив  C  содержит  номера  вершин  –  k-ый  элемент  C  есть  номер
предпоследней вершины на текущем кратчайшем пути из начальной вершины  в  k-
ю. Используется также Matrix – матрица расстояний.
 Опишем алгоритм Дейкстры:
 1 (инициализация). В цикле от 1 до  n  заполнить  значением  False  массив
Visited; заполнить  числом  i  массив  C  (i  –  номер  стартовой  вершины);
перенести i-ю строку матрицы Matrix в массив Len;
Visited[i]:=True; C[i]:=0;
 2 (общий шаг). Найти минимум среди неотмеченных (т.е. тех к,  для  которых
Visitid[k]=False);  пусть   минимум   достигается   на   индексе   j,   т.е.
Len[j](Len[k];
Затем выполнять следующие операции:
Visited[i]:=True;
если Len[k]>Len[j]+Matrix[j, k], то (Len[k]:=Len[j]+Matrix[j, k]; C[k]:=j)
{Если все Visited[k] отмечены, то длина пути от [pic] до [pic]  равна  C[k].
Теперь надо перечислить вершины, входящие в кратчайший путь}.
 3 (выдача ответа). {Путь от [pic] до [pic]  выдается  в  обратном  порядке
следующей процедурой:}
1   z:=C[k];
2   Выдать z
3   z:=C[z]. Если z =0, то конец,
иначе перейти к 3.2.
 Теорема. Алгоритм Дейкстры – корректен.
 Доказательство. Теорему докажем по индукции.  Рассмотрим  1-й  шаг,  когда
находится  min  Len[k]  (k(i),  пусть  минимум  достигается  на  вершине  j.
Остальные [pic](k(i, j) пока лишь верхние  оценки  длин  путей  из  [pic]  в
[pic](они могут  уменьшаться  в  ходе  выполнения  алгоритма,  но  Len[j]  –
окончательная длина пути [[pic]  …  [pic]],  совпадающего  с  дугой  [[pic],
[pic]].  Если  бы  существовал  путь  короче,   он   бы   выглядел   [[pic],
[pic]…[pic]], но уже первая его  дуга  не  меньше,  чем  весь  путь  [[pic],
[pic]], а остальные дуги имеют положительную длину).
 Мы разбили все вершины на два класса: С  –  неотмеченных  вершин  и  С’  –
отмеченных вершин. После 1-го общего шага [pic],  [pic](  С’,  и,  очевидно,
все кратчайшие пути (пока “все” – означает “один”) из v’(С’ не содержат  v(С
в качестве промежуточной.
 Теперь  сделаем  индуктивный  шаг.  Уже  проделано  s  общих  шагов,   уже
С’={[pic], [pic], [pic], …, [pic]}, при этом все кратчайшие пути из [pic]  в
v’ не содержат вершин из С в качестве промежуточных.
 Найдем  минимальное  Len[l]  в  неотмеченных   столбцах;   пусть   минимум
достигается на вершине [pic].  Соответственный элемент [pic],  меняясь,  мог
принимать только номера отмеченных  вершин,  значит  в  вершину  [pic]  идет
путь,  где  все  вершины,  кроме  конечной  [pic],  –   штрихованные,   т.е.
принадлежащие С’. Любой другой путь [[pic] … [pic]], содержащий хотя бы  еще
одну не штрихованную  вершину, будет длиннее. Теорема доказана.

Uses Crt;
Const MaxSize=10;
      Infinity=1000;
Var    Mattr: array [1..MaxSize, 1..MaxSize] of integer;
     Visited: array [1..MaxSize] of boolean;
    Len,Path: array [1..MaxSize] of integer;
   n, Start, Finish, k, i: integer;

 Procedure Init;
 Var  f: text;
      i, j: integer;
 Begin
   Assign(f, INPUT.MTR');
   Reset(f);
   Readln(f, n);
   For i:=1 to n do
   Begin
    For j:=1 to n do Read(f, mattr[i,j]);
    Readln(f)
   End;
   Write('Начальная вершина: '); Readln(Start);
   For i:=1 to n do
   Begin
     Visited[i]:=False;
     Len[i]:=Mattr[Start, i];
     Path[i]:=Start
   End;
   Path[Start]:=0;
   Visited[Start]:=True
 End;

 Function Possible: Boolean;
 Var i: integer;
 Begin
   Possible:=True;
   For i:=1 to n do If not Visited[i] then Exit;
   Possible:=False
 End;

 Function Min: Integer;
 Var i, minvalue, currentmin: integer;
 Begin
   Minvalue:=Infinity;
   For i:=1 to n do
     If not Visited[i] then
       If Len[i]Len[k]+Mattr[i, k] then
                                  Begin
                                    Len[i]:=Len[k]+Mattr[i, k];
                                    Path[i]:=k
                                 End
  End;
  Write('Конечная вершина: '); Readln(Finish);
  Write(Finish);
  Finish:=Path[Finish];
  While Finish<>0 do
  Begin
    Write('<-', Finish);
    Finish:=Path[Finish];
  End;
  ReadKey
End.
 Например, для сети, описанной в предыдущей главе, кратчайший путь из  3-ей
вершины в 8-ю будет: 8(2(3.


смотреть на рефераты похожие на "Aлгоритмы на графах"