Caută drumul cel mai scurt

De obicei, calea de pe problema graficului de căutare poate fi formulată după cum urmează: a găsi cel mai bun traseu. Sub cel mai bun traseu, ca regulă, să înțeleagă mai scurt. Găsiți cel mai scurt traseu posibil alegerea tuturor găsit. Cu toate acestea, nu este necesar să se caute toate rutele.

Puteți face altfel: atunci când selectarea punctului următor pentru a verifica dacă lungimea nu va depăși lungimea traseului format deja găsit calea, în cazul în care acest punct vor fi incluse în traseu; În cazul în care aceasta depășește, că acest punct ar trebui să fie omise, și alegeți o altă.

Astfel, după prima rută este găsit, programul va căuta numai pentru acele ramuri ale grafului, care pot îmbunătăți soluția găsită de tăiere cale, ceea ce face traseul mai formase deja găsit.

Listarea 12.6 prezintă o procedură care utilizează o procedură pas care efectuează selectarea următorul punct, astfel încât să puteți căuta calea de lungime minimă.

Listarea 12.6. Caută drumul cel mai scurt

Procedura TForm1.Button1Click (Expeditor: TObject);

// Karta.map [i, j] nu este 0, dacă

// punctele i și j sunt conectate

// Road - numărul de card de puncte

inclusiv: array [1..n] de boolean; // inclusiv [1] este adevărat, în cazul în care punctul

// numărul i este inclus în drum

// începe și puncte finale

găsit: boolean; len: integer; // lungime găsită (minimă)

// Route> c_len: integer; // lungime curent (format)

// Selectați punctul următor