Mozes da uradis sa obicnim backtrackom. Nabi u jednu matricu NxN brojke tako da je na mestu A,B udaljenost grada A od B ili -1 ako nisu povezani putem. Ovim si opisao graf povezanosti. Onda napravi niz tipa Boolean kojim kontrolises da li je grad preko koga prolazis vec usao u sastav puta, jer ti petlje u grafu sigurno nisu potrebe. Treba ti jos jedna varijabla u kojoj cuvas minimalni put, i obicna rekurzija da to obradi...
recimo:
const maxn=200;
var veze: array [maxn, manx] of integer;
min, put, i, n, A, B: integer;
ukljucen: array[1..maxn] of Boolean;
// ovde dodje kod koji strpa podatke iz grida u matricu veze
// u n je broj gradova, A i B su gradovi izmedju kojih trazis rastojanje
for i:=1 to n do ukljucen
:=n;
min:=MaxInt; //ili neki veliki broj od kog je minimalno rastojanje sigurno manje...
put:=0;
procedure Obidji(g : integer);
var cik: integer;
begin
ukljucen[g]:=true;
if (g=B) and (put<min) do min:=put;
for cik:=1 to n do
if (veze[g, cik]<>-1) and (not ukljucen[cik]) do
begin
put:=put+veze[g, cik];
Obidji(cik);
put:=put-veze[g, cik];
end;
uklucen[g]:=false;
end;
procedureu pozivas sa Obidji(A); i u min pokupi najkrace rastojanje.
Javi ako ima bug, da ispravljamo....
BTW: Sigurno ima dobrih heuristika ili brand&bacch-ova za ovo ali nemam kad da se majem sa time sada...
10 BEGIN
20 HOME_SWEET_HOME
30 GOTO 20