program a_kwr1;             (* KWR 1 mit Startpunktwahl, Thomas Klein  1999 *)
uses graph,grafik,tsp;
var anfang:stadtnr;
    laenge:array [1..maxstadt] of entfernung;
    wege:array [1..maxstadt] of string[maxstadt];

procedure dijkstra_w(w:weg);
 (* berechnet kuerzeste Wege ohne in w enthaltene Punkte,
    Startpunkt: Endpunkt v. w, Ergebnis in laenge, wege *)
 var anfang,n,i,j,k,k0,anzahl_vorlaeufig:stadtnr;
     index,vorlaeufig,vorgaenger:array [1..maxstadt] of stadtnr;
     min,pfadlaenge:entfernung;
 begin
  (* Index auf nicht in w enthaltene Staedte erstellen *)
  i:=ord(w[length(w)]); delete(w,length(w),1); n:=0;
  for j:=1 to stadtanzahl do
   if pos(chr(j),w)=0 then begin
    inc(n); index[n]:=j;
    if j=i then anfang:=n;
   end else begin
    wege[j]:=''; laenge[j]:=maxentfernung;
   end;
  (* Dijkstra-Algorithmus *)
  for j:=1 to n do begin
   vorlaeufig[j]:=j; vorgaenger[j]:=anfang;
   laenge[index[j]]:=entftab[index[anfang],index[j]];
   wege[index[j]]:=chr(index[anfang])+chr(index[j]);
  end;
  vorlaeufig[anfang]:=n; anzahl_vorlaeufig:=n-1;
  for i:=1 to n-1 do begin
   min:=maxentfernung;
   for k:=1 to anzahl_vorlaeufig do begin
    j:=vorlaeufig[k];
    pfadlaenge:=laenge[index[anfang]]+entftab[index[anfang],index[j]];
    if pfadlaenge<laenge[index[j]] then begin
     vorgaenger[j]:=anfang;
     laenge[index[j]]:=pfadlaenge;
     wege[index[j]]:=wege[index[anfang]]+chr(index[j]);
    end;
    if laenge[index[j]]<min then begin
     min:=laenge[index[j]]; k0:=k;
    end;
   end;
   anfang:=vorlaeufig[k0]; vorlaeufig[k0]:=vorlaeufig[anzahl_vorlaeufig];
   dec(anzahl_vorlaeufig);
  end;
 end;

procedure kwr1(var w:weg);
 (* K�rzeste-Wege-Rundreise, Staedtezahl max. *)
 var anfang,i,mweg,m,l:stadtnr;
 begin
  anfang:=ord(w[length(w)]);
  while length(w)<stadtanzahl do begin
   dijkstra_w(w);
   m:=0;
   for i:=1 to stadtanzahl do
    if (wege[i]<>'') and (i<>ord(w[length(w)])) then begin
     l:=length(wege[i]);
     if l>m then begin m:=l; mweg:=i; end;
    end;
   delete(w,length(w),1); w:=w+wege[mweg];
  end;
  w:=w+chr(anfang);
 end;

function auto_kwr1(var mweg:weg):stadtnr;
 (* automatische Bestimmung des besten Startpunktes *)
 var i,anfang:stadtnr;
     m,l:entfernung;
     w:weg;
 begin
  m:=maxentfernung;
  for i:=1 to stadtanzahl do begin
   w:=chr(i); kwr1(w); l:=weglaenge(w);
   if l<m then begin m:=l; mweg:=w; anfang:=i; end;
  end;
  auto_kwr1:=anfang;
 end;

begin
 if tspinit('TSP: K�rzeste-Wege-Rundreise 1(max. St�dtezahl) mit Startpunktwahl',
            'Berechnen') then
  while tspmenue([0..255]) do begin
   start; anfang:=auto_kwr1(aktuell); stop;
   wegkarte(aktuell,true,brown,yellow); farbstadt(anfang,white);
   laenge_aus(aktuell); zeit_aus(true);
  end;
 closegraph;
end.