unit Graf;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, Grids, StdCtrls, DBCtrls, Buttons, ExtCtrls,
  BinaryTrees;

type
  TMainForm = class(TForm)
    SGValues: TStringGrid;
    Panel1: TPanel;
    BFillGrid: TBitBtn;
    BClear: TBitBtn;
    BCalculate: TBitBtn;
    Panel2: TPanel;
    BCityAdd: TBitBtn;
    BCityDel: TBitBtn;
    ENewCityName: TEdit;
    LBCities: TListBox;
    Label3: TLabel;
    MInfo: TMemo;
    BCityClear: TBitBtn;
    BRandomValues: TBitBtn;
    procedure BCityAddClick(Sender: TObject);
    procedure BFillGridClick(Sender: TObject);
    procedure BCalculateClick(Sender: TObject);
    procedure BCityDelClick(Sender: TObject);
    procedure BCityClearClick(Sender: TObject);
    procedure BRandomValuesClick(Sender: TObject);
    procedure FormCreate(Sender: TObject);
    procedure BClearClick(Sender: TObject);
  private
    { Private declarations }

  public
    { Public declarations }
  end;

var
  MainForm: TMainForm;

implementation

{$R *.dfm}

// Заполняем матрицу расстояний из таблицы расстояний //
function FillMatrixFromGrid(Grid: TStringGrid; Count: Integer): TIntMatrix;
var
  I, J,               // Счетчики
  Code: Integer;      // dummy
begin
  SetLength(Result, Count);
  For I:=0 to Count-1 do
    begin
      SetLength(Result[I], Count);
      For J:=0 to Count-1 do
        Val(Grid.Cells[I+1, J+1], Result[I, J], Code);
    end;
end;

// Процедура создает дерево всех возможных путей от начального города до других городов без повторений //
// Корневым элементом является город, от которого производится поиск путей //
procedure CreateRoadsTree(Roads: TIntMatrix; Tree: TBinaryTree);
var
  I: Integer;
  Child: TBinaryTree;
begin
  for I:=Low(Roads)to High(Roads)do
    if(Roads[Tree.Index, I]>0)then
      if not(Tree.FindParent(I))then
        begin
          Child:=TBinaryTree.Create(I, Roads[Tree.Index, I], Tree);
          CreateRoadsTree(Roads, Child);
        end;
end;

// Процедура добавляет новый город и обновляет таблицу расстояний //
procedure TMainForm.BCityAddClick(Sender: TObject);
begin
  if(ENewCityName.Text='')then                              // Если не указано название...
    ShowMessage('Ошибка: Вы не ввели название города!')       // Ругаемся
      else                                                  // Иначе...
    begin                                                   // Если название указано...
      LBCities.Items.Add(ENewCityName.Text);                  // Добавляем новый город в список
      ENewCityName.Text:='';                                  // Очищаем поле ввода имени для нового города
      BFillGrid.Click;                                        // Обновляем таблицу расстояний
    end;
end;

// Процедура удаляет город из списка городов и обновляет таблицу расстояний //
procedure TMainForm.BCityDelClick(Sender: TObject);
begin
  if(LBCities.ItemIndex=-1)then                             // Если не указано название...
    ShowMessage('Ошибка: Вы не указали какой город нужно удалить!')   // Ругаемся
      else                                                  // Иначе...
    begin                                                   // Если название указано...
      LBCities.Items.Delete(LBCities.ItemIndex);              // Удаляем элемент из списка
      BFillGrid.Click;                                        // Обновляем таблицу расстояний
    end;
end;

// Процедура очищает список городов и обнволяет таблицу расстояний //
procedure TMainForm.BCityClearClick(Sender: TObject);
begin
  LBCities.Items.Clear;
  BFillGrid.Click;
end;

// Процедура заполняет таблицу именами городов и очищает //
procedure TMainForm.BFillGridClick(Sender: TObject);
var
  I: Integer;
begin
  SGValues.ColCount:=LBCities.Items.Count+1;    // Количество столбцов
  SGValues.RowCount:=LBCities.Items.Count+1;    // Количество строк

  if(SGValues.ColCount>1)then SGValues.FixedCols:=1;
  if(SGValues.RowCount>1)then SGValues.FixedRows:=1;
  
  for I:=0 to LBCities.Items.Count-1 do
    begin
      SGValues.Cells[I+1, 0] := LBCities.Items[I];  
      SGValues.Cells[0, I+1] := LBCities.Items[I];
    end;

  BClear.Click;                                 // Очищу таблицу
end;

// Процедура придумывает расстояния между городами // 
procedure TMainForm.BRandomValuesClick(Sender: TObject);
var
  I, J,           // Счетчики цикла
  Len: Integer;   // Временная переменная расчет расстояния
  RoadExists: Byte;  // Существование дороги

begin
  BClear.Click;                               // Очищаем таблицу

  for I:=1 to LBCities.Items.Count-1 do
    for J:=I+1 to LBCities.Items.Count do
      begin
        RoadExists:=Random(100);              // Будет ли дорога
        if(RoadExists<10)then                 // Если дорога существует (вероятность того что дорога существует = 70%)
          begin
            Len:=Random(200)+20;                // Придумаем расстояние
            SGValues.Cells[I, J]:=IntToStr(Len);// Заполняем
            SGValues.Cells[J, I]:=IntToStr(Len);// Заполняем
          end;
      end;
end;

// Процедура заполняет нулями таблицу расстояний //
procedure TMainForm.BClearClick(Sender: TObject);
var
  I, J: Integer;
begin
  for I:=1 to LBCities.Items.Count do
    for J:=1 to LBCities.Items.Count do
      SGValues.Cells[I, J]:='';
end;

// Процедура производит расчеты расстояний от города до города //
procedure TMainForm.BCalculateClick(Sender: TObject);
var
  FirstTown,          // Индекс начального города
  I, J: Integer;      // Счетчики
  Len: Integer;       // Временная переменная для расчета расстояния
  RoadsTree,          // Дерево путей
  FChild: TBinaryTree;  // Ветка путей - для расчета длины пути
  Path: TIntArray;    // Поиск путей
  S: String;          // Временная переменная для вывода в Memo
begin
  MInfo.Lines.Clear;                                // Очистка Memo

  FirstTown:=LBCities.ItemIndex;                    // Определяем начальный город
  if(FirstTown=-1)then                              // Если не указан начальный город
    begin
      ShowMessage('Ошибка: Вы не указали начальный город!');  // Ругаемся
      Exit;
    end;

  RoadsTree:=TBinaryTree.Create(FirstTown, 0, nil); // Создаю корень дерева путей, корнем является начальный город
  CreateRoadsTree( FillMatrixFromGrid(SGValues, LBCities.Count), RoadsTree );   // Создаю дерево всех путей от начального города

  For I:=0 to LBCities.Count-1 do                   // Обходим все города
    if(I<>FirstTown)then
      begin
        Path:=RoadsTree.PathToChild(I);             // Ищем кратчайший путь от начального города до города I
        S:=LBCities.Items[FirstTown];
        Len:=0;                                     // Определяю расстояние между городами
        FChild:=RoadsTree;
        For J:=High(Path)-1 downto Low(Path)do
          begin
            FChild:=FChild.FindChild( Path[J] );
            Len:=Len+FChild.LengthToParent;
            S:=S+' => '+LBCities.Items[ Path[J] ];
          end;
        if(Len=0)then                               // Если расстояние нулевое, значит нет пути между городами (даже через другие города)
          MInfo.Lines.Add(S+' => '+LBCities.Items[I]+' - не найден путь') // Вывожу информацию
        else
          MInfo.Lines.Add(S+' = '+IntToStr(Len));                         // Вывожу информацию
      end;

end;

procedure TMainForm.FormCreate(Sender: TObject);
begin
  // По умолчанию при запуске программы создаются 4 города
  ENewCityName.Text:='Город 0';
  BCityAdd.Click;
  ENewCityName.Text:='Город 1';
  BCityAdd.Click;
  ENewCityName.Text:='Город 2';
  BCityAdd.Click;
  ENewCityName.Text:='Город 3';
  BCityAdd.Click;

  // Случайно заполняем таблицу растсояний
  BRandomValues.Click;
  // Выделяем первый город
  LBCities.ItemIndex:=0;
  // Производим расчет расстояний от первого города до остальных
  BCalculate.Click;
end;

end.