Naprej: Slovarček BBS-arskega slenga Višje: Mere središčnosti Nazaj: Rezultati

Fletcherjev algoritem

Na začetku se delamo, kot da v dani točki ne vidimo dlje od sosedne točke: g[i,j]:=1, če je med točkama kakšna povezava, ali 0 sicer, d[i,j]:=1, če sta točki povezani, ali BIG (neskončno), če ni povezave. Potem izvedemo naslednji algoritem.

  for k := 1 to n do begin
     for i := 1 to n do
        for j := 1 to n do begin
           dst := min( BIG, d[i,k]+d[k,j]);
           if d[i,j]  dst then begin
              cnt := g[i,k]*g[k,j];
              if d[i,j] = dst then
                 g[i,j] := g[i,j] + cnt
              else begin
                 g[i,j] := cnt;
                 d[i,j] := dst
              end {else}
           end {if d  dst}
        end; {for j}
     d[k,k] := 0;
     g[k,k] := 1
  end; {for k}

Na koncu je d matrika dolžin geodetk, g pa matrika števila geodetk med dvema točkama.