Зазвичай завдання пошуку шляху на графі формулюється так: знайти найкращий маршрут. під найкращим маршрутом, як правило, розуміють найкоротший. Знайти найкоротший маршрут можна вибором з усіх знайдених. Однак зовсім не обов’язково шукати всі маршрути.
Можна вчинити інакше: під час вибору черговий точки перевірити, чи не перевищить довжина формованого маршруту довжину вже знайденого шляху, якщо ця точка буде включена в маршрут; якщо перевищить, то цю точку слід пропустити і вибрати іншу.
Таким чином, після того як буде знайдений перший маршрут, програма буде вести пошук тільки по тим гілкам графа, які можуть поліпшити знайдене рішення, відсікаючи шляхи, які роблять формований маршрут довший вже знайденого.
У лістингу 12.6 приведена процедура, яка використовує процедуру step, що виконує вибір черговий точки маршруту таким чином, що забезпечується пошук шляху мінімальної довжини.
Лістинг 12.6. Пошук найкоротшого шляху
procedure TForm1.Button1Click (Sender: TObject);
const
N = 10; { кол-во вершин графа} va r < / b>
map: array [1..N, 1..N] of integer;
// Карта.map [i, j] НЕ 0, якщо
// точки i і j з'єднані
road: array [1..N] of integer;
// Дорога - номери точок карти
incl: array [1..N] of boolean; // incl [1] дорівнює TRUE, якщо точка
// з номером i включена в road
start, finish: integer;
// Початкова і кінцева точки
found: boolean; len: integer; // довжина знайденого (мінімального)
// маршруту} c_len: integer; // довжина поточного (формованого)
// маршруту i, j: integer;
// вибір черговий точки
procedure step (s, f, p: integer);
var
з: integer; {Номер точки, в яку робимо черговий крок}
i: integer; begin
if s = f then begin
len: = c_len; { збережемо довжину знайденого маршруту}
{ висновок знайденого маршруту}
for i: = 1 to p-1 do
Label1.caption: = Label1.caption + ' '+ IntToStr (road [i]);
Label1.caption: = Label1.caption
+ ', довжина: '+ IntToStr (len) + # 13;
end
else
{ вибираємо чергову точку}
for c: = l to N do {перевіряємо всі вершини}
if (map [s, c] <> 0) and (NOT incite])
and ((len = 0) or (c_len + map [s, c] & lt; len)) then begin
// точка з'єднана з поточної, але не включена в
// маршрут
roadtp]: = c; { додамо вершину в шлях}
incl [c]: = TRUE; { пометим вершину як включену}
c_len: = c_len + map [s, с];
step (c, f, p + l);
incite]: = FALSE; roadtp]: = 0;
c_len: = c_len-map [s, с];
end;
end;
{ кінець процедури step}
begin
Labell.caption: = '';
{ ініціалізація масивів}
for i: = 1 to N do road [i]: = 0;
for i: = l to N do incl [i]: = FALSE;
{ введення опису карти з SrtingGrid.Cells}
for i: = l to N do
for j: = 1 to N do
if StringGridl.Cells [i, j] <>"
then mapti, j]: = StrToInt (StringGridl.Cells [i, j] )
else mapti, j]: = 0;
len: = 0; // довжина знайденого (мінімального) маршруту з
len: = 0, - // довжина поточного (формованого) маршруту
start: = StrToInt (Edit1.text);
finish: = StrToInt (Edit2.text);
road [1]: = start; { внесемо точку в маршрут}
incl [start]: = TRUE; { пометим її як включену}
step (start, finish, 2); {шукаємо другу точку маршруту}
// перевіримо, чи знайдений хоча б один шлях
if not found
then Label1.caption: = 'Зазначені крапки не з'єднані!';
end;
Діалогове вікно програми пошуку найкоротшого шляху і процедура обробки події OnActivate нічим не відрізняються від діалогового вікна і відповідної процедури OnActivate програми пошуку всіх можливих маршрутів, розглянутої в попередньому розділі.