Решение задачи о кратчайшем маршруте методом Форда
1. Постановка сетевой транспортной задачи.


На практике часто встречается задача определения кратчайшего маршрута по заданной сети из начального пункта до конечного пункта маршрута. Транспортная сеть может быть представлена в виде графа (рис.1), дуги которого - транспортные магистрали, а узлы - пункты отправления и назначения. Графически транспортная сеть изображается в виде совокупности n пунктов P₁,P₂,...,P_n, причем некоторые упорядоченные пары (P_i,P_j) пунктов назначения соединены дугами заданной длинны r(P_i,P_j)=l_ij. Некоторые или все дуги могут быть ориентированы, т.е. по ним возможно движение только в одном направлении, указанном стрелками.

На рис.1 построена ориентированная транспортная сеть, содержащая шесть пунктов P₁,P₂,...,P₆, которые связаны между собой восьмью транспортными путями.

Необходимо определить кратчайший маршрут из пункта P₁ в P₆. Определение кратчайшего маршрута состоит в указании последовательности прохождения маршрута через промежуточные пункты и суммарной длинны маршрута.

Например маршрут из пункта P₁ в пункт P₆: P₁P₂P₄P₆; L=l₁₂+l₂₄+l₄₆=10.

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

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

Рассмотрим подробнее каждый из этих четырех этапов.
2.1 Первый этап: Составление исходной таблицы расстояний.
Данная таблица содержит n+1 строк и такое же количество столбцов; P_i - пункты отправления; P_j - пункты назначения. Во второй строке и втором столбце проставляется значения параметров l_i иl_j, определение значений которых производятся на втором этапе решения задачи. В остальных клетках таблицы проставляются значения расстояний l_ij из i-го пункта в j-й пункт. Причем заполняем клетки таблицы, лежащие выше главной диагонали. Если пункт P_i не соединен отрезком пути с пунктом P_j, то соответствующая клетка таблицы не заполняется.
2.2 Второй этап: Определение l_i и l_j.
   Определяется значение параметров в соответствии с формулой:
l_j=min(l_i+l_ij); i=1,2,...,n; j=1,2,...,n, (1)

где l₁=0.

Эти значения заполняются во второй строке и во втором столбце.
2.3 Третий этап: Определение длинны кратчайших путей.
   Возможны два случая определения длинны кратчайших путей из пунктов Pi в пункты P_j, i=1,2,...,n; j=1,2,...,n.

   В первом случае, если выполняются неравенство:
l_j - l_i £ l_ij; l_ij¹0; j=1,2,...,n; j=1,2,...,n, (2)

то значения параметров l₁,...,l_n удовлетворяют условиям оптимальности. Каждое значение l_j есть не что иное, как кратчайшее расстояние от пункта P_i до пункта P_j, j=2,3,...,n.

Во втором случае, если для некоторых клеток (i,j) таблицы имеет место неравенство:
l_j - l_i > l_ij; i=1,...,n; j=1,...,n, (3)

то значения l_j и l_i могут быть уменьшены.

Если справедливо (3), тогда исправим значение l_j0, пересчитав его по формуле:

l¢_j0=l_i0+l_i0j0. (4)
2.4 Четвертый этап: Нахождение кратчайшего пути.
   Определения последовательности пунктов кратчайшего маршрута. С этой целью для каждого столбца определяют величину:

l_r1,j = l_j - l_r1, (5)

где l_r1,j берется из таблицы, причем l_r1 выбирается так, чтобы выполнилось равенство (5). Таким образом определим r1. Далее продолжим ту же операцию, но будем считать, последней не P_n, а P_r1. Будем продолжать до тех пор, пока r_n=1.

   Таким образом кратчайший маршрут проходит через P_r1,P_r2,...,P_rn, а длинна маршрута Lmin=l_r2,r1+l_r3,r2+...+l_rn-1,rn.

3. Описание программы.
   Программа “FORD” написана на языке высокого уровня - Pascal, в интегрированной среде разработки “Turbo Pascal 7.0” фирмы Borland Inc.

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

   В программе предусмотрена возможность повторного решения задачи с другими исходными данными.
4. Описание подпрограмм и процедур.
Подпрограммы и функции.

ТИП	НАЗВАНИЕ	НАЗНАЧЕНИЕ
Function type : real	min;	Вычисляет минимальное значение вектора k[i];
Procedure	set_graph_mode;	Устанавливает графический режим;
Procedure	install_firewall;	Инициализирует огонь;
Procedure	fire;	Процедура рисования огня;
Procedure	ok;	Выводит сообщение о корректности операции;
Procedure	notok;	Выводит сообщение о некорректности операции;
Procedure	check_input_data;	Проверяет корректность ввода данных;
Procedure	keybord_input;	Ввод исходных данных с клавиатуры;
Procedure	ramka;	Выводит рамку по краям экрана;
Procedure	save;	Сохранение результатов в файл;
Procedure	about_program;	Выводит информацию о программе;
Procedure	about_method;	Выводит информацию о методе Форда;
Procedure	output_graph;	Рисует вершины графа;
Procedure	draw_ways;	Рисует дуги графа;
Procedure	draw_short_way;	Рисует кратчайший маршрут;
Procedure	count_point_coord;	Вычисляет экранные координаты вершин графа;
Procedure	set_font;	Инициализирует шрифт пользователя;
Procedure	calculate;	Основное математическое ядро программы;
Procedure	draw_menu;	Открытие меню;
Procedure	redraw_menu;	Закрытие меню;
Procedure	main_menu;	Основной механизм меню;
Procedure	pixel;	Ставит точку;
Procedure	stars;	Инициализирует массив со звездами;
Procedure	welcomescreen;	Заставка;

PROCEDURE draw_short_way;

begin

for i:=1 to lenth-1 do

 begin

 setlinestyle(0,0,3);

 setcolor(red);

 x:=result[i];

 y:=result[i+1];

 x1:=round(coord_point[x,1]);

 y1:=round(coord_point[x,2]);

 x2:=round(coord_point[y,1]);

 y2:=round(coord_point[y,2]);

 line(x1,y1,x2,y2);

 end;

settextstyle(chrus,0,1);

setcolor(14);

outtextxy(50,370,'Кратчайший маршрут: ');

for i:=1 to lenth do

 begin

 str(result[lenth-i+1],o);

 outtextxy(300+i*15,370,o);

 end;

outtextxy(50,400,'Длинна кратчайшего маршрута: ');

str(round(mas[0,n]),o);

outtextxy(420,400,o);

end;
PROCEDURE count_point_coord;

begin

 pi1:=(2*pi)/n;

 m:=0;

 aa:=3*pi/2;

 for i:=1 to n do

 begin

 coord_point[i,1]:=(cos(aa)*150)+300;

 coord_point[i,2]:=(sin(aa)*150)+200;

 aa:=aa+pi1;

 end;

end;
PROCEDURE set_font;

begin

chrus:=installuserfont('fn03');

settextstyle(chrus,0,2);

end;
PROCEDURE calculate;

begin

for i:=1 to n do

 k[i]:=0;

clrscr;

mas[0,1]:=0;

mas[1,0]:=0;

{3}

 for j:=2 to n do

 begin

 for i:=1 to n do

 if (mas[0,i]<>-1) and (mas[i,j]<>-1)

 then k[i]:=mas[0,i]+mas[i,j]

 else k[i]:=-1;

 mas[0,j]:=min;

 mas[j,0]:=mas[0,j];

 end;

{4}

repeat

 l:=true;

 for i:=1 to n do

 for j:=1 to n do

 if (mas[0,j]-mas[0,i]>mas[i,j]) and (mas[i,j]<>-1) then

 begin

 l:=false;

 mas[0,j]:=mas[0,i]+mas[i,j];

 end;

until l;

{5}

j:=n;

m:=1;

t:=0;

for i:=1 to n do

 result[i]:=-1;

result[1]:=n;

repeat

 inc(m);

 for i:=1 to j do

 begin

 if (mas[i,j]<>-1) and (i<>j) and (mas[i,j]=mas[0,j]-mas[0,i])

 then

 begin

 t:=i;

 break;

 end;

 end;

 result[m]:=t;

 j:=t;

 lenth:=m;

until j=1;

calculatedata:=true;

ok;

end;
PROCEDURE stars;

begin

for i:=1 to 500 do

 begin

 starx[i]:=round(random(640));

 stary[i]:=round(random(480));

 starc[i]:=round(31-random(16));

 end;

end;
PROCEDURE draw_menu;

begin

cleardevice;

for i:=1 to 500 do

 putpixel(starx[i],stary[i],starc[i]);

cursor:=1;

lastcursor:=cursor;

 for i:=1 to 260 do

 begin

 setcolor(8);

 line(210+i,110,210+i,110);

 setcolor(4);

 line(200+i,100,200+i,100);

 end;

 for j:=1 to nline*30+10 do

 begin

 setcolor(8);

 line(210,110+j,470,110+j);

 setcolor(4);

 line(200,100+j,460,100+j);

 end;

setcolor(0);

for j:=1 to nline do

 outtextxy(220,110+(j-1)*25,menu[menulevel,j]);

end;
PROCEDURE redraw_menu;

begin

 for j:=nline*30+10 downto 1 do

 begin

 setcolor(0);

 line(210,110+j,470,110+j);

 line(200,100+j,210,100+j);

 setcolor(8);

 if j<10 then

 begin

 setcolor(0);

 line(210,100+j,470,100+j);

 end

 else

 line(210,100+j,470,100+j);

 end;

 for i:=260 downto 0 do

 begin

 putpixel(210+i,110,0);

 putpixel(200+i,100,0);

 end;

cleardevice;

end;
PROCEDURE main_menu;

begin

settextstyle(chrus,0,2);

draw_menu;

repeat

 setcolor(0);

 outtextxy(220,110+(lastcursor-1)*25,menu[menulevel,lastcursor]);

 setcolor(7);

 outtextxy(220,110+(cursor-1)*25,menu[menulevel,cursor]);

 pressed:=readkey;

 if pressed=#0 then

 begin

 pressed:=readkey;

 move:=false;

 if (pressed=#80) and (cursor=nline) then

 begin

lastcursor:=nline; cursor:=1;

move:=true;

 end;

 if (pressed=#72) and (cursor=1) then

 begin

lastcursor:=1;

cursor:=nline;

move:=true;

 end;
 if (pressed=#80) and (cursor<nline) and not(move) then

 begin

lastcursor:=cursor;

inc(cursor);

 end;

 if (pressed=#72) and (cursor>1) and not(move) then

 begin

lastcursor:=cursor;

dec(cursor);

 end;

 end;

until pressed=#13;

redraw_menu;

if cursor=5 then about_program;

if cursor=4 then about_metod;

if (cursor=1) and (menulevel=3) then keyboard_input;

if (cursor=1) and (menulevel=4) then

 begin

 closegraph;

 halt;

 end;

if (cursor=2) and (menulevel=1) and (inputdata=false) then notok;

if (cursor=2) and (menulevel=1) and (inputdata=true) then

 begin

count_point_coord;

draw_ways;

output_graph;

 end;

if (cursor=2) and (menulevel=0) and (inputdata=true) then calculate;

if (cursor=2) and (menulevel=0) and (inputdata=false) then notok;

if (cursor=1) and (menulevel=2) and (calculatedata=false) then notok;

if (cursor=1) and (menulevel=2) and (calculatedata=true) then

 begin

count_point_coord;

draw_ways;

draw_short_way;

output_graph;

 end;

if (cursor=2) and (menulevel=2) and (calculatedata=true) then save;

if (cursor=2) and (menulevel=2) and (calculatedata=false) then notok;

if (cursor=2) and (menulevel=3) then notok;

menulevel:=menugo[menulevel,cursor];

nline:=menuof[menulevel];

main_menu;

end;
PROCEDURE welcomescreen;

begin

settextstyle(chrus,0,1);

randomize;

install_firewall;

 for i:=0 to messize do

 begin

 setcolor(4);

 outtextxy(10,iii*step+i*30,title[i]);

 end;

repeat

 fire;

until keypressed;

end;
BEGIN

for i:=0 to 20 do

 for j:=0 to 20 do

 mas[i,j]:=-1;

stars;

inputdata:=false;

calculatedata:=false;

menulevel:=0;

nline:=menuof[menulevel];

z2:=0;

set_graph_mode;

set_font;

welcomescreen;

closegraph;

z2:=2;

set_graph_mode;

main_menu;

repeat until keypressed;

END.