Опpеделение кpатчайшего пути на сети с циклами

 

j = 1:

 

 

j = 1  2  3   4  5  6  7 v_j – u₁  *  2  5  11  7  *  * d_1j *  2  8  11 9  *  *

 

Поскольку v_j-u_i £ d_ij для всех j, величины v_j пересчитывать не следует. Заметим, что для j=1, 6 и 7 расстояния d_ij не определены, поэтому эти вели- чины при сравнении не берутся. В процессе реализации алгоритма обнару- живается, что условие оптимальности первый раз нарушается при i=6.

При i = 6 условие оптимальности нарушается для j = 4 и 5. Величины v₄

 

и v₅ изменяются следующим образом:

 

v ^/₄ = u₆ + d₆₄ = 3+5=8 (v₄=u₄=8),

 

v ^/₅ =u₆ + d₆₅ =3+1= 4 (v₅ =u₅=4).

 

В последующих вычислениях, т.е. для i=7, используются изменённые значения v₄ , v₅ и u₄ , u₅.

_{j = 2:}

 

 

 

 

 

 

 

 

j = 3: j = 4: j=5: 

j = 1 2 3 4 5 6 7

 

v_j – u₂ -2 * 3 * 5 1 *

d_2j 4 * 3 * 5 1 *

 

 

j = 1 2 3 4 5 6 7

 

v_j – u₃ -5 -3 * 6 * -2 *

^d_3j ^1 4 * ¥ ^* 2 *

 

 

j = 1 2 3 4 5 6 7

 

v_j – u₄ -11 * -6 * * -8 2

d_4j 5 * 9 * * 2 23

 

 

j = 1 2 3 4 5 6 7

 

v_j – u₅ -7 -5 * * * -4 6

^d_5j ² ¥ ^{* * * 7 9}

 

j = 6:

 

 

 

 

 

 

 

j =7: 

 

 

 

j = 1 2 3 4 5 6 7

 

v_j – u₆ * -1 2 8 4 * 10

d_6j * 8 3 5 1 * 10

 

 

j = 1 2 3 4 5 6 7

 

v_j – u₇ * * * -5 -9 -10 *

^d_7j ^{* * * 10 4 2 *}

 

 

После этого повторяется шаг 2 с изменёнными значениями v_j  и u_i. В таблице 3 приведены результаты сравнений, проведённых для i =1, 2, … ,7. Из этой таблицы видно, что в новых изменениях уже нет необходимости, и по- этому последние изменённые величины v_j дают длину кратчайшего пути от 1 _{до j.}

 

Покажем, каким образом используется u_i и v_j в таблице 2 для определения кратчайших расстояний между узлом 1 и каждым из узлов j=2, 3, … , 7. Проиллюстрируем процедуру на примере нахождения участков кратчайшего п ути между узлами 1 и 7.

Как уже известно, кратчайшее расстояние между узлами 1 и 7 равно v₇ =

 

13. Определение участков сети должно начинаться с узла 7. Требуется найти узел, непосредственно предшествующий узлу 7. Из столбца 7 таблицы 2 видно, что равенство v₇ =u₁ + d₁₇ , выполняется при i=5 и i=6, т. е. либо узел 5, либо узел 6 соединён с 7 (альтернативные решения).

Рассмотрим сначала узел 5. Из столбца 5 видно, что равенство v₅=u₁+d₁₅ выполняется при i=6. Далее из столбца 6 следует, что равенство v₆=u₁+d₁₆ вы- полняется при i=2. Наконец, как следует из столбца 2, равенство v₂=u₁+d₁₂ выполняется при i=1. Получившиеся участки дают путь 1®2®6®5®7 с v₇

_=13.

 

Аналогичная процедура позволяет получить другой кратчайший путь между узлами 1 и 7, а также все пути между узлами 1 и j = 2, 3, 4, 5 и 6.

 

 

 

 

^{j =1 2 3 4 5 6 7 u}_i 

Таблица 3

 

i =1 _* 2

_* 2

i =2 -2 _*

⁴ _* 

5 8 4

8 11 9

3 _* 2

³ _* ⁵ 

* * ⁰

* *

1 _* 2

¹ _*

 

i =3 -5 -3 _*

^1 4 _* 

3 _* -2 _* 5

_* ² _*

 

i =4 -8

5 

_* -3 _*

_* ⁹ _* 

_* -5 5 8

_* ^2 23

 

i =5 -4

2 

-2 _* *

_* * 

_* -1 9 4

_* ^7 9

 

i = 6 _*

*

i = 7 _*

_* 

-1 2

8 3

 

* *

_* * 

5 1

5 1

5 -9

10 4 

*

*

-10

2 

10 3

10

_* 13

_*

 

ЛИСТИНГ ПРОГРАММЫ

 

Алгоритм Форда-Беллмана

 

var a:array[1..20,1..20] of word; {матрица смежности}

c,pred,fl,d:array[1..20] of word;{c - массив кратчайших расстояний; pred - массив предыдущих вершин; fl - массив флагов; d - массив для записи пути}

i,j,k,n,first,last:byte;

f:text;{переменная для  открытия in.txt}

 

{процедура обхода  графа вглубь для поиска всех  путей}

 

Procedure Dfs(x:word); {в качестве  параметра передаём текущую вершину}

var i:byte; {локальная переменная}

begin

if x=last then {если конечная  вершина, то вводим путь}

  begin

   write(first,' ');

   for i:=1 to j do {выводим путь}

    write(d[i],' ');

    writeln;

    exit;{выходим из процедуры}

  end;

fl[x]:=1; {помечаем что  были в вершине}

for i:=1 to n do {если не  были в вершине и существует  дуга в неё}

  if (fl[i]=0)and(a[x,i]<>32767) then

   begin

    inc(j);

    d[j]:=i; {записываем  в путь вершину}

    dfs(i);

    dec(j);

   end;

 fl[x]:=0; {помечаем что вершина свободна}

end;

 

{основная программа}

 

begin

     assign(f,'in.txt'); {открываем файл для чтения}

     reset(f);

     readln(f, n); {считываем  количество вершин}

     for i:=1 to n do

          for j:=1 to n do

          read(f,a[i,j]); {считываем матрицу смежности}

     writeln('Mатрица:');

     for i:=1 to n do  {выводим матрицу на экран}

          for j:=1 to n do

           if j=n then writeln(a[i,j])

           else write(a[i,j],' ');

     for i:=1 to n do {заменяем нули бесконечностью}

          for j:=1 to n do

          if a[i,j]=0 then a[i,j]:=32767;

     writeln('Введите 1 вершину: ');

     readln(first);

     writeln('Введите 2 вершину');

     readln(last);

     close(f); {закрываем файл in.txt}

     for j:=1 to n do

     begin

           c[j]:=a[first,j]; {записываем начальные значения}

           if a[first,j]<32767 then

           pred[j]:=first; {если существует дуга  то записываем предыдущую вершину}

     end;

     for i:=3 to n do

         for j:=1 to n do

             if j<>first then

             for k:=1 to n do  {если не бесконечность и путь более выгодный}

                 if (c[k]<32767) and (c[k]+a[k,j]<c[j]) then

                  begin

                   c[j]:=c[k]+a[k,j]; {записываем новое значение}

                   pred[j]:=k; {записываем pred вершину}

                  end;

     if c[last]=32767 then writeln('Нет путей')

     else {если бесконечность то нет пути}

      begin

          writeln;

          writeln('Кратчайший путь:');

          write(first,' ');

          i:=last;

          k:=1;

          while i<>first do {в обратном порядке  обходим путь}

           begin

               d[k]:=i; {записываем путь в массив}

               k:=k+1;

               i:=pred[i];

           end;

          for i:=k-1 downto 1 do {выводим кратчайший путь}

          write(d[i],' ');

          writeln;

          writeln('Все пути:');

          j:=0;

          Dfs(first); {вызываем процедуру поиска  всех путей}

      end;

     readln;

     readln;

end.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ЗАКЛЮЧЕНИЕ

 

В данной курсовой работе мною была раскрыта тема «Определение кратчайшего пути на сети с циклами». Эта тема является достаточно важной в рассмотрении вопросов системного анализа.

В своей работе я привел задачи, решение которых осуществляется с помощью сетевых моделей:

• минимизация сети;

• кратчайший путь:

• сеть без циклов;
• сеть с циклами;

• определение максимального потока;

Метод «Определение кратчайшего пути на сети с циклами» теоретически рассмотрен более подробно и к этому методу предложена программа, написанная на языке программирования Pascal.

Эта программа облегчает  понимание данного метода и дает яркую картину принципа его работы.

 При написании курсовой работы была использована различного рода литература.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ЛИТЕРАТУРА

 

1. Дегтярев Ю.И. Методы оптимизации: Учеб. пособие для ВУЗов.-М.: Сов.радио, 1980.-272с.

 

2. Дегтярев Ю.И. Исследование операций: Учеб. пособие для ВУЗов по спец.АСУ. -М.: Высш. шк., 1986.-320с.: ил.