Решение задачи о кратчайшем маршруте

Решение задачи о кратчайшем маршруте методом Форда 1. Постановка сетевой транспортной задачи. На практике часто встречается задача определения кратчайшего маршрута по заданной сети из начального пункта до конечного пункта маршрута. Транспортная сеть может быть представлена в виде графа рис.1, дуги которого - транспортные магистрали, а узлы - пункты отправления и назначения. Графически транспортная сеть изображается в виде совокупности

n пунктов P1,P2 Pn, причем некоторые упорядоченные пары Pi,Pj пунктов назначения соединены дугами заданной длинны Pi,Pjlij. Некоторые или все дуги могут быть ориентированы, т.е. по ним возможно движение только в одном направлении, указанном стрелками. На рис.1 построена ориентированная транспортная сеть, содержащая шесть пунктов P1,P2 P6, которые связаны между собой восьмью транспортными путями.

Необходимо определить кратчайший маршрут из пункта P1 в P6. Определение кратчайшего маршрута состоит в указании последовательности прохождения маршрута через промежуточные пункты и суммарной длинны маршрута. Например маршрут из пункта P1 в пункт P6 P1P2P4P6 Ll12l24l4610. Постановка задачи приобретает смысл в том случае, если имеется несколько вариантов маршрута

из начального пункта в конечный. В этом случае физический смысл функции цели задачи состоит в минимизации общей длинны маршрута, т.е. в определении кратчайшего пути из P1 в Pn. 2. Описание метода и алгоритма решения. Метод Форда бал разработан специально для решения сетевых транспортных задач и основан, по существу, на принципе оптимальности. Алгоритм метода Форда содержит четыре этапа схема 1.

На первом этапе производится заполнение исходной таблицы расстояний от любого i-го пункта в любой другой j-й пункт назначения. На втором этапе определяются для каждого пункта некоторые параметры i и j по соответствующим формулам. Далее на третьем этапе определяются кратчайшие расстояния. Наконец, на четвертом этапе определяются кратчайшие маршруты из пункта отправления Р1 в любой другой пункт назначения Рj, j1,2 n. Рассмотрим подробнее каждый из этих четырех этапов.

2.1 Первый этап Составление исходной таблицы расстояний. Данная таблица содержит n1 строк и такое же количество столбцов Pi - пункты отправления Pj - пункты назначения. Во второй строке и втором столбце проставляется значения параметров i иj, определение значений которых производятся на втором этапе решения задачи. В остальных клетках таблицы проставляются значения расстояний lij из i-го пункта в j-й пункт.

Причем заполняем клетки таблицы, лежащие выше главной диагонали. Если пункт Pi не соединен отрезком пути с пунктом Pj, то соответствующая клетка таблицы не заполняется. 2.2 Второй этап Определение i и j. Определяется значение параметров в соответствии с формулой jminilij i1,2 n j1,2 n, 1 где 10. Эти значения заполняются во второй строке и во втором столбце.

2.3 Третий этап Определение длинны кратчайших путей. Возможны два случая определения длинны кратчайших путей из пунктов Pi в пункты Pj, i1,2 n j1,2 n. В первом случае, если выполняются неравенство j - i lij lij0 j1,2 n j1,2 n, 2 то значения параметров 1 n удовлетворяют условиям оптимальности. Каждое значение j есть не что иное, как кратчайшее расстояние от пункта

Pi до пункта Pj, j2,3 n. Во втором случае, если для некоторых клеток i,j таблицы имеет место неравенство j - i lij i1 n j1 n, 3 то значения j и i могут быть уменьшены. Если справедливо 3, тогда исправим значение j0, пересчитав его по формуле j0i0li0j2.4 Четвертый этап Нахождение кратчайшего пути. Определения последовательности пунктов кратчайшего маршрута. С этой целью для каждого столбца определяют величину lr1,j j - r1, 5 где lr1,j берется из таблицы,

причем r1 выбирается так, чтобы выполнилось равенство 5. Таким образом определим r1. Далее продолжим ту же операцию, но будем считать, последней не Pn, а Pr1. Будем продолжать до тех пор, пока rn1. Таким образом кратчайший маршрут проходит через Pr1,Pr2 Prn, а длинна маршрута Lminlr2,r1lr3,r2 lrn-1,rn. 3. Описание программы. Программа FORD написана на языке высокого уровня -

Pascal, в интегрированной среде разработки Turbo Pascal 7.0 фирмы Borland Inc. Программа предназначена для нахождения кратчайшего пути в сетевом графе по методу Форда. Программа легка в использовании, что достигается за счет использования дружественного интерфейса и иерархического меню. Вначале программы производится ввод данных, затем нахождение кратчайшего маршрута и вычисление его длинны, далее выводится результат.

Вывод результатов возможен как в файл, так и на экран. В программе предусмотрена возможность повторного решения задачи с другими исходными данными. 4. Описание подпрограмм и процедур. Подпрограммы и функции. ТИП НАЗВАНИЕ НАЗНАЧЕНИЕFunction type realminВычисляет минимальное значение вектора kiProceduresetgraphmodeУстанавливает графический режимProcedureinstallfirewallИнициализир ует огоньProcedurefireПроцедура рисования огняProcedureokВыводит

сообщение о корректности операцииProcedurenotokВыводит сообщение о некорректности операцииProcedurecheckinputdataПроверяет корректность ввода данныхProcedurekeybordinputВвод исходных данных с клавиатурыProcedureramkaВыводит рамку по краям экранаProceduresaveСохранение результатов в файлProcedureaboutprogramВыводит информацию о программеProcedureaboutmethodВыводит информацию о методе ФордаProcedureoutputgraphРисует вершины графаProceduredrawwaysРисует дуги графаProceduredrawshortwayРисует

кратчайший маршрутProcedurecountpointcoordВычисляет экранные координаты вершин графаProceduresetfontИнициализирует шрифт пользователяProcedurecalculateОсновное математическое ядро программыProceduredrawmenuОткрытие менюProcedureredrawmenuЗакрытие менюProceduremainmenuОсновной механизм менюProcedurepixelСтавит точкуProcedurestarsИнициализирует массив со звездамиProcedurewelcomescreenЗаставка 4.2 Таблица идентификаторов. ИМЯ тИП НАЗНАЧЕНИЕКонстантыmenuarray of stringОписывает меню программыmenuofarray

of byteОписывает меню программыmenugoarray of byteОписывает меню программыname1stringИмя файла входных данныхname2stringИмя файла выходных данныхxxxwordРазмер огня по хyyywordРазмер огня по уxx1wordКоордината х огняyy1wordКоордината у огняmessizebyteРазмер заглавияtitlearray of stringЗаглавиеПеременныеmasarray of realОсновная матрица вычисленийcoordpointarray of realКоординаты вершин графаiintegerПеременная для организации циклаjintegerПеременная для организации циклаtintegerИспользуется при расчете путиmintegerСчетчик

кол-ва вершин в крат. ПутиnintegerКол-во вершин в графеzintegerКод ошибкиx1integerИсп. в процедуре вывода на экранy1integerИсп. в процедуре вывода на экранx2integerИсп. в процедуре вывода на экранy2integerИсп. в процедуре вывода на экранkkintegerПромежуточное значениеiiiintegerПромежуточное значениеxintegerКоордината х конца отрезкаyintegerКоордината у конца отрезкаlenthintegerКол-во вершин в кратчайшем маршрутеchrusintegerНомер шрифта пользователяz1integerНомер графического драйвервz2integerНомер графического режимаkarray of realИспользуется

для нахождения минимумаresultarray of integerНомера вершин, которые входят в кратчайший маршрутerrorcodearray of byteКоды ошибок при вводе данныхfire1array of byteХранит цвета огняfire2array of byteМатрица промежуточных данныхaarealИспользуется при вычислении координат вершин графаpi1realИспользуется при вычислении координат вершин графаsrealХранит промежуточное значениеlbooleanИсп. при определении кратчайшего маршрутаinputdatabooleanTRUE, если данные вводилисьcalculatedatabooleanTRUE, если данные били обработаныmovbooleanИспользуется в

процедуре менюostringИспользуется при вводе с клавиатурыtempbyteХранит временное значениеcursorbyteКоординаты курсора менюlastcursorbyteПоследние координаты курсора менюmenulevelbyteУровень менюnlinebyteКол-во строк в текушем уровне менюpressedcharИспользуется при вводе с клавиатурыf1textФайловая переменнаяf2textФайловая переменная 5. Примеры решения контрольных задач. Исходная таблица расстояний для одного из вариантов ранжированного графа PiPj1234561X532X253X774X35X26X

После обработки таблицы с заданными исходными данными, программа выдает следующие результаты - кратчайший маршрут 1-2-4-6 - длинна кратчайшего маршрута 10 Исходная таблица расстояний для одного из вариантов не ранжированного графа PiPj1234561X1622X138X42X5513X96X После обработки таблицы с заданными исходными данными, программа выдает следующие результаты - кратчайший маршрут 1-5-4-2-6 - длинна кратчайшего маршрута 8 Программа работоспособна при любых других вариантах

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

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

Форда при различных исходных данных. PROGRAM ford uses crt,graph const menuarray0 4,1 6 of string Ввод данных,Решение задачи,Вывод результата, О методе,О программе,Выход, Ввод данных,Просмотр данных,Назад Экран,Файл,Назад Клавиатура,Файл,Назад Да,Нет menuofarray0 4 of byte 6,3,3,3,2 menugoarray0 4,1 6 of byte 1,0,2,0,0,4, 3,0,0,0,0,0, 0,0,0,0,0,0, 0,0,1,0,0,0, 0,0,0,0,0,0 name1input.dat name2output.dat

xxx140 yyy20 xx110 yy1140 messize3 colarray16 31 of byte0,186,113,4,40,41,41,42,42,43,44,69, 15,15,15,15 titlearray0 messize of string АЛГОРИТМИЧЕСКИЕ МЕТОДЫ, ИССЛЕДОВАНИЯ ОПЕРАЦИЙ Метод Форда type matr array0 20,0 20 of real coord array 1 20,1 2 of real var masmatr coordpointcoord i,j,t,m,n,z,x1,y1,x2,kk,iii,y2,x,y,lenth ,chrus,z1,z2integer karray1 20 of real resultarray1 20 of integer errorcodearray1 5 of byte fire1array1 yyy,1 xxx of byte fire2array1 yyy,1

xxx of byte maskarray1 6 of byte starxarray1 500 of word staryarray1 500 of word starcarray1 500 of byte aa,cc,pi1,sreal l,inputdata,calculatedata,moveboolean ostring temp,cursor,lastcursor,menulevel,nline,s tepbyte pressedchar f1,f2text FUNCTION minreal begin s0 for i1 to n do if s0 and ki -1 then ski else ifki s and ki -1 then ski mins end PROCEDURE setgraphmode begin z1installuserdriversvga256,nil initgraphz1,z2, cleardevice end PROCEDURE pixelxwordy,colbyte begin asm mov bx,x mov cl,y mov dl,col

mov ax,0a000h mov es,ax mov al,0a0h mul cl add ax,ax add bx,ax mov esbx,dl end end PROCEDURE installfirewall begin for i1 to yyy do for j1 to xxx do begin fire1i,j0 fire2i,j0 end end PROCEDURE fire begin for i1 to yyy-1 do for j1 to xxx do begin pixelj2xx1,i3yy1,colfire1i,j pixelj2xx1,i3yy1-1,colfire1i,j pixelj2xx1,i3yy1-2,colfire1i,j end for j1 to xxx do begin kkrandom8 if kk 3 then fire1yyy,j16 else fire1yyy,jround31-kk end for iyyy-1 downto 1 do for j2 to xxx-1 do begin fire2i,jroundfire1i1,jfire1i1,j-1fire1i1

,j1-random43 if fire2i,j 16 or fire2i,j 31 then fire2i,j16 end for i1 to yyy do for j1 to xxx do fire1i,jfire2i,j end PROCEDURE ok begin cleardevice setcolor1 rectangle120,100,520,220 rectangle100,120,540,200 setcolor14 outtextxy180,130,Опeрация произведена outtextxy250,160,корректно. repeat until keypressed end PROCEDURE notok begin cleardevice setcolor4 rectangle120,100,520,220 rectangle100,120,540,200 setcolor14 outtextxy180,130,Опeрация произведена outtextxy230,160,не корректно. repeat until keypressed end

PROCEDURE checkinputdata begin inputdatatrue for i1 to 5 do errorcodei0 for i0 to n do begin if masi,1 -1 then errorcode11 if masn,i -1 then errorcode21 if masi,i -1 then errorcode31 end for i1 to n do for j1 to n do begin if masi,j -1 and masj,i -1 then errorcode41 if masi,j 0 and masi,j -1 then errorcode51 end clrscr if errorcode1 0 then writelnОшибка Не существует истока. if errorcode2 0 then writelnОшибка Не существует стока. if errorcode3 0 then writelnОшибка

Существует дуга из одной вершины в ту же вершину. if errorcode4 0 then writelnОшибка Существует две дуги из одной вершины в другую. if errorcode5 0 then writelnОшибка Существует дуга с отрицительной нагрузкой. for i1 to 5 do if errorcodei 0 then inputdatafalse if z 0 or roundn n or n 2 or n 20 then inputdatafalse calculatedatafalse end PROCEDURE keyboardinput begin z0 closegraph clrscr writeВведите колличество пунктов2-20 readlno valo,

n,z if z 0 or roundn n or n 2 or n 20 then checkinputdata writeln Введите нагрузку. Если дуга не существует, то нажмите Enter. writeln for i1 to n-1 do for ji to n do if i j then begin write Введите нагрузку от ,i й вершины до ,j й вершины readlno if o then valo,masi,j,z else masi,j-1 if z 0 then exit end checkinputdata setgraphmode settextstylechrus,0,2 if inputdatatrue then ok else notok

end PROCEDURE ramka begin cleardevice setcolor1 rectangle30,10,610,470 rectangle10,30,630,450 end PROCEDURE save begin assignf2,name2 rewritef2 writef2,Кратчайший маршрут for i1 to lenth do writef2,resultlenth-i1 writelnf2, writef2,Длинна кратчайшего маршрута writef2,roundmas0,n closef2 ok end PROCEDURE aboutprogram begin ramka settextstylechrus,0,5 setcolor14 outtextxy160,30,О программе settextstylechrus,0,1 setcolor12 outtextxy40,100,Программа outtextxy40,150,Версия outtextxy40,175,Назначение outtextxy40,240,Автор

outtextxy40,265,Дата setcolor8 outtextxy200,100,Решение задачи о кратчайшем outtextxy200,120,маршруте методом Форда. outtextxy200,150,v1.0 outtextxy200,175,Курсовой проект по дисциплине outtextxy200,195,Алгоритмические методы иссле- outtextxy200,215,дования опираций outtextxy200,240, outtextxy200,265,декабрь 1998 года setcolor11 outtextxy50,395,для большей информации смотрите README.TXT repeat until keypressed end PROCEDURE aboutmetod begin ramka settextstylechrus,0,5 setcolor14

outtextxy130,30,О методе Форда settextstylechrus,0,1 setcolor8 outtextxy40,90,Метод Форда был разработан специально для outtextxy50,110,решения сетевых транспортных задач и осно- outtextxy50,130,ван, по существу на принципе оптимальности. outtextxy40,150,Алгоритм метода Форда содержит четыре этапа. outtextxy50,170,На первом этапе производится заполнение ис- outtextxy50,190,ходной таблицы расстояний от любого i-го outtextxy50,210,пункта в любой другой j-й пункт назначения outtextxy50,230,На

втором этапе определяются для каждого outtextxy50,250,пункта некоторые параметры Ai и Aj по соот- outtextxy50,270,ветствующим формулам и правилам. Далее на outtextxy50,290,третьем этапе определяется кратчайшее рас- outtextxy50,310,стояние. Наконец, на четвертом этапе опре- outtextxy50,330,деляются кратчайшие маршруты из пункта outtextxy50,350,отправления Р1 в любой пункт назначения Рj, outtextxy50,370,j2,3 n. repeat until keypressed end

PROCEDURE outputgraph begin settextstylechrus,0,1 for i1 to n do begin setcolor10 fillellipseroundcoordpointi,1,roundcoord pointi,2,15,15 setcolor15 stri,o if i 9 then outtextxyroundcoordpointi,1-12, roundcoordpointi,2-12,o else outtextxyroundcoordpointi,1-7, roundcoordpointi,2-12,o end repeat until keypressed end PROCEDURE drawways begin settextstylechrus,0,2 for i1 to n do for j1 to n do if masi,j -1 then begin x1roundcoordpointi,1 y1roundcoordpointi,2 x2roundcoordpointj,1 y2roundcoordpointj,2 setcolor15 linex1,y1,x2,y2

temproundmasi,j strtemp,o setcolor2 outtextxyroundx1x225,roundy1y225,o end end PROCEDURE drawshortway begin for i1 to lenth-1 do begin setlinestyle0,0,3 setcolorred xresulti yresulti1 x1roundcoordpointx,1 y1roundcoordpointx,2 x2roundcoordpointy,1 y2roundcoordpointy,2 linex1,y1,x2,y2 end settextstylechrus,0,1 setcolor14 outtextxy50,370,Кратчайший маршрут for i1 to lenth do begin strresultlenth-i1,o outtextxy300i15,370,o end outtextxy50,400,Длинна кратчайшего маршрута strroundmas0,n,o outtextxy420,400,o

end PROCEDURE countpointcoord begin pi12pin m0 aa3pi2 for i1 to n do begin coordpointi,1cosaa150300 coordpointi,2sinaa150200 aaaapi1 end end PROCEDURE setfont begin chrusinstalluserfontfn03 settextstylechrus,0,2 end PROCEDURE calculate begin for i1 to n do ki0 clrscr mas0,10 mas1,00 3 for j2 to n do begin for i1 to n do if mas0,i -1 and masi,j -1 then kimas0,imasi,j else ki-1 mas0,jmin masj,0mas0,j end 4 repeat ltrue for i1 to n do for j1 to n do if mas0,j-mas0,i masi,j and masi,j -1 then begin lfalse mas0,jmas0,imasi,

j end until l 5 jn m1 t0 for i1 to n do resulti-1 result1n repeat incm for i1 to j do begin if masi,j -1 and i j and masi,jmas0,j-mas0,i then begin ti break end end resultmt jt lenthm until j1 calculatedatatrue ok end PROCEDURE stars begin for i1 to 500 do begin starxiroundrandom640 staryiroundrandom480 starciround31-random16 end end PROCEDURE drawmenu begin cleardevice for i1 to 500 do putpixelstarxi,staryi,starci cursor1 lastcursorcursor for i1 to 260 do begin setcolor8 line210i,110,210i,110 setcolor4 line200i,100,200i,100 end for j1 to

nline3010 do begin setcolor8 line210,110j,470,110j setcolor4 line200,100j,460,100j end setcolor0 for j1 to nline do outtextxy220,110j-125,menumenulevel,j end PROCEDURE redrawmenu begin for jnline3010 downto 1 do begin setcolor0 line210,110j,470,110j line200,100j,210,100j setcolor8 if j 10 then begin setcolor0 line210,100j,470,100j end else line210,100j,470,100j end for i260 downto 0 do begin putpixel210i,110,0 putpixel200i,100,0 end cleardevice end

PROCEDURE mainmenu begin settextstylechrus,0,2 drawmenu repeat setcolor0 outtextxy220,110lastcursor-125,menumenul evel,lastcursor setcolor7 outtextxy220,110cursor-125,menumenulevel ,cursor pressedreadkey if pressed0 then begin pressedreadkey movefalse if pressed80 and cursornline then begin lastcursornline cursor1 movetrue end if pressed72 and cursor1 then begin lastcursor1 cursornline movetrue end if pressed80 and cursor nline and notmove then begin lastcursorcursor inccursor end if pressed72 and cursor 1 and notmove

then begin lastcursorcursor deccursor end end until pressed13 redrawmenu if cursor5 then aboutprogram if cursor4 then aboutmetod if cursor1 and menulevel3 then keyboardinput if cursor1 and menulevel4 then begin closegraph halt end if cursor2 and menulevel1 and inputdatafalse then notok if cursor2 and menulevel1 and inputdatatrue then begin countpointcoord drawways outputgraph end if cursor2 and menulevel0 and inputdatatrue then calculate if cursor2 and menulevel0 and inputdatafalse then notok if cursor1 and

menulevel2 and calculatedatafalse then notok if cursor1 and menulevel2 and calculatedatatrue then begin countpointcoord drawways drawshortway outputgraph end if cursor2 and menulevel2 and calculatedatatrue then save if cursor2 and menulevel2 and calculatedatafalse then notok if cursor2 and menulevel3 then notok menulevelmenugomenulevel,cursor nlinemenuofmenulevel mainmenu end PROCEDURE welcomescreen begin settextstylechrus,0,1 randomize installfirewall for i0 to messize do begin

setcolor4 outtextxy10,iiistepi30,titlei end repeat fire until keypressed end BEGIN for i0 to 20 do for j0 to 20 do masi,j-1 stars inputdatafalse calculatedatafalse menulevel0 nlinemenuofmenulevel z20 setgraphmode setfont welcomescreen closegraph z22 setgraphmode mainmenu repeat until keypressed END.