Курсовая работа: Алгоритмы на графах. Кратчайшие расстояния на графах

A := y2-y1;

B := x1-x2;

C := y1*(x2-x1)-x1*(y2-y1);

Подстановкой координат (x3,y3) в уравнение прямой Ax+By+C=0, построенной по первым двум точкам (x1,y1) и (x2,y2) и с учетом крайних случаев, когда прямая параллельна осям координат, вычисляем, был ли поворот левым или правым и соответственно устанавливаем значение функции CountTime.

Left := (((x2>x1) and ((A*x3+B*y3+C)<0))) or

(((x2<x1) and ((A*x3+B*y3+C)<0))) or

(((y2=y1) and (x1>x2) and (y3<y1))) or

(((y2=y1) and (x1<x2) and (y3>y1))) or

(((x2=x1) and (y1>y2) and (x3>x1))) or

(((x2=x1) and (y1<y2) and (x3<x1))) ;

if Left then CountTime:=K*D[i2]

else CountTime:=0;

"Сравнение пути с оптимальным" выполняется следующим образом:

inc(kv); sled[kv]:=G[i,j,1];

T := Time[i]+G[i,j,2] + CountTime;

if T < OptT

then begin

OptT:=T;

OptKv:=kv; OptSled:=Sled;

end;

Sled[kv]:=0; dec(kv);

Таким образом, оптимальное время хранится в переменной OptT а оптимальный путь храниться в массиве OptSled с количеством элементов OptKv. И потому, вывод результатов выглядит так:

writeln(OptT);

fori:=1 toOptKvdowriteln(OptSled[i]);

Полный текст программы приводится ниже

program by98d2s2;

Const

FREE = 1;

DONE = 2;