Алгоритм Дейкстры - нахождение кратчайшего маршрута до каждой вершины

  TMyGraph = class
    vertexNum: Integer;
    vertexSource: Integer;
 
    // input parameters
    vertexWeightsArray: array of array of Integer; // матрица с весами
    vertexNamesArray: array of String;
    edgesNamesArray: array of array of Char;
 
    // temp parameters
    vertexVisitedArray: array of  Boolean;
    routesVertexArray: array of Integer;
 
    // output parameters
    distances: array of Integer;
    paths: array of Integer;
  private
    procedure ReadFromFile;
  public
    procedure Init(_totalVertexNum, _vertexSource: Integer);
    procedure FindShortestPaths;
    function getPath(myVertex: Integer): String;
    function getPreviousVertex(vertex: Integer): Integer;
    procedure DrawResults(lv: TListView);
  end;
 
implementation
{ TGraph }
 
procedure TMyGraph.ReadFromFile;
var
  f: text;
  i, j: integer;
begin
  vertexWeightsArray := nil;
  AssignFile(f, 'input/input.txt');
  Reset(f);
  i := -1;
  while not Eof(f) do
  begin
    Inc(i);
    SetLength(vertexWeightsArray, i + 1);
    j:= -1;
    while not Eoln(f) do
    begin
      Inc(j);
      SetLength(vertexWeightsArray[i], j + 1);
      Read(f, vertexWeightsArray[i, j]);
    end;
    ReadLn(f);
  end;
  CloseFile(f);
 
  vertexNamesArray := nil;
  // тут считаем названия вершин
  AssignFile(f, 'input/names.txt');
  Reset(f);
  i := -1;
  while not Eof(f) do
  begin
    while not Eoln(f) do
    begin
      Inc(i);
      SetLength(vertexNamesArray, i + 1);
      Read(f, vertexNamesArray[i]);
    end;
    ReadLn(f);
  end;
  CloseFile(f);
 
  // тут считаем названия ребер
  edgesNamesArray := nil;
  AssignFile(f, 'input/edges.txt');
  Reset(f);
  i := -1;
  while not Eof(f) do
  begin
    Inc(i);
    SetLength(edgesNamesArray, i + 1);
    j:= -1;
    while not Eoln(f) do
    begin
      Inc(j);
      SetLength(edgesNamesArray[i], j + 1);
      Read(f, edgesNamesArray[i, j]);
      if edgesNamesArray[i, j] = ' ' then
        Dec(j);
    end;
    ReadLn(f);
  end;
  CloseFile(f);
end;
 
procedure TMyGraph.Init(_totalVertexNum, _vertexSource: Integer);
var
  i: Integer;
begin
  vertexNum := _totalVertexNum;
  vertexSource := _vertexSource-1;
 
  SetLength(distances, vertexNum);
  SetLength(vertexVisitedArray, vertexNum);
  SetLength(routesVertexArray, vertexNum);
 
  for i:=0 to 8 do
    routesVertexArray[i] := vertexSource;
 
  ReadFromFile;
end;
 
procedure TMyGraph.FindShortestPaths;
var count, index, i, u, min: integer;
begin
  for i:=0 to vertexNum-1 do
  begin
    distances[i]:=infinity;
    vertexVisitedArray[i]:=false;
  end;
  distances[vertexSource]:=0;
  for count:=1 to vertexNum-2 do
  begin
    min:=infinity;
    for i:=0 to vertexNum-1 do
    if (not vertexVisitedArray[i]) and (distances[i]<=min) then
    begin
      min:=distances[i]; index:=i;
    end;
    u:=index;
    vertexVisitedArray[u]:=true;
    for i:=0 to vertexNum-1 do
      if (not vertexVisitedArray[i]) and (vertexWeightsArray[u, i]<>0) and
      (distances[u]<>infinity) and (distances[u]+vertexWeightsArray[u, i]<distances[i]) then
      begin
        distances[i]:=distances[u]+vertexWeightsArray[u, i];
        routesVertexArray[i] := u;
      end;
  end;
end;
 
function TMyGraph.getPath(myVertex: Integer): String;
var
  curVertex, prevVertex, i: Integer;
  output: String;
begin
  i:=0;
  curVertex := myVertex;
  repeat
    SetLength(paths, i+1);
    paths[i] := curVertex;
    prevVertex := getPreviousVertex(curVertex);
    curVertex := prevVertex;
    Inc(i);
  until curVertex=vertexSource;
  SetLength(paths, i+1);
  paths[i] := curVertex;
 
  //output := vertexNamesArray[vertexSource] + ' ';
  while(i>0)do
  begin
    output := output + ' -('+ edgesNamesArray[paths[i], paths[i-1]] +')-> ' + vertexNamesArray[paths[i-1]];
    Dec(i);
  end;
  Result := output;
end;
 
function TMyGraph.getPreviousVertex(vertex: Integer): Integer;
begin
  Result := routesVertexArray[vertex];
end;
 
procedure TMyGraph.DrawResults(lv: TListView);
var
  i: Integer;
begin
  for i:=0 to vertexNum-1 do
  if i<>vertexSource then
  begin
    begin
      with lv.Items.Add do
      begin
        Caption := vertexNamesArray[i];
        SubItems.Add(IntToStr(distances[i]));
        SubItems.Add(getPath(i));
      end;
    end;
  end;
end;