алгоритм нахождения наилучшего маршрута между двумя заданными городами

[Uli9]

Здравствуйте всем! У меня проблема. Очень нужно реализовать алгоритм нахождения наилучшего маршрута между двумя заданными городами, если при этом ему надо обязательно попасть в заданный пользователем города. На Delphi. Буду очень благодарна.Плиииз((((Хотя бы что-нибудь((

[Arigato]

В чем выражается наилучшесть? В кратчайшем пути или пути с наименьшим весом? Данные в виде графа или как?

[tools]

Ну, конечно, лучше всего с графами сделать эту задачку. Достаточно взять книгу по дискретной математике или просто по теории графов, в разделе задач о кратчайших соединениях и путях. Например, Ерусалимского могу посоветовать. В нем неплохо описаны алгоритмы Дейкстры и Краскала. А если это задание по программированию, то можно подойти к преподавателю по дискретной математике и попросить совета у него.Вот.

[Uli9]

Нужно кратчайшие пути. Денные не в виде графа.Просто выбираются 3 города.Пользователем.И в окошко Memo выводится расчет расстояний между ними.Вот и все.Пожалуйста помогите(((((

[Arigato]

Денные не в виде графа.Просто выбираются 3 города.Пользователем.И в окошко Memo выводится расчет расстояний между ними

Т.е. будут 3 отрезка (длинну которых можно определить):
(X1, Y1) - (X2, Y2) - между 1-м и 2-м городом
(X1, Y1) - (X3, Y3) - между 1-м и 3-м
(X2, Y2) - (X3, Y3) - между 2-м и 3-м
Из этих данных можно сделать простецкий граф, вес ребра - расстояние между городами.

[Uli9]

Вот у меня например уже реализован алгоритм Дейкстры для другого случая. А мне нужно найти расстояние между двумя городами( которые выберет сам пользователь) и обязательно зайти в третий промежуточный город, который тоже выберет сам пользователь. Я не знаю как это сделать к сожалению. Подскажите пожалуйста(



unit Unit1;

interface

uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, Grids,Buttons;
const
MAXPATH = 1000; // максимальная длина пути м/д двумя вершинами

MAXTOWNCOUNT = 100; // максимальное количество вершин

type
TForm1 = class(TForm)
memRes: TMemo;
sgWeights: TStringGrid;
lbTowns: TListBox;
editTownName: TEdit;
btnAddTown: TButton;
btnDeleteTown: TButton;
btnClear: TButton;
btnGo: TButton;
btnSetTowns: TButton;
btnGenerate: TButton;
Label1: TLabel;
Label2: TLabel;
Label3: TLabel;
Label4: TLabel;
lblFirstTown: TLabel;
lblMAXPATH: TLabel;
Label5: TLabel;
Label6: TLabel;
ComboBox1: TComboBox;
ComboBox2: TComboBox;
Memo1: TMemo;
Button1: TButton;
procedure btnAddTownClick(Sender: TObject);
procedure btnSetTownsClick(Sender: TObject);
procedure sgWeightsSetEditText(Sender: TObject; ACol, ARow: Integer;
const Value: String);
procedure btnGenerateClick(Sender: TObject);
procedure btnClearClick(Sender: TObject);
procedure btnDeleteTownClick(Sender: TObject);
procedure FormShow(Sender: TObject);
procedure btnGoClick(Sender: TObject);
procedure ComboBox1Change(Sender: TObject);
procedure ComboBox2Change(Sender: TObject);
private
{ Private declarations }

// матрица весов (расстояний между городами)
Weights: array [0..MAXTOWNCOUNT-1, 0..MAXTOWNCOUNT-1] of integer;
// количество городов

towncount: integer;
// массивы для расчета
// город (вершина графа) уже обсчитан
Ready: array [0..MAXTOWNCOUNT-1] of boolean;
// текущий кратчайший пусть до этого города из первого

Paths: array [0..MAXTOWNCOUNT-1] of word;
// предпоследний узел пути из первого города до этого

Nodes: array [0..MAXTOWNCOUNT-1] of byte;
// индекс первого города

first: integer;
// очистка интерфейсной таблицы весов
procedure ClearGrid;
// перенести данные из TStringGrid в матрицу весов
procedure GetWeightsMatrix;
// инициализируем расчет

procedure FirstCountStep;
// запускаем расчет
procedure GoCount;
// результаты - в мемо
procedure ShowResults;
// все ли вершины обсчитаны?

function AllAreReady: boolean;
// получить необсчитанную вершину с наименьшим путем
function GetMinPath: word;

public
{ Public declarations }
end;

var
Form1: TForm1;

implementation

{$R *.dfm}uses Unit2;

procedure TForm1.btnAddTownClick(Sender: TObject); //Добавить город в список
begin
if editTownName.Text='' then

MessageDlg('Ошибка: Вы не ввели название города!', mtError, [mbOK], 0)
else begin

lbTowns.Items.Add(editTownName.Text );
editTownName.Text := '';
end;

end;

procedure TForm1.btnSetTownsClick(Sender: TObject); //Заполнить шапку таблицы названиями городов из списка

var
i: integer;
begin
sgWeights.ColCount := lbTowns.Items.Count+1;
sgWeights.RowCount := lbTowns.Items.Count+1;
for i:=0 to lbTowns.Items.Count-1 do begin

sgWeights.Cells[i+1,0] := lbTowns.Items[i];
sgWeights.Cells[0,i+1] := lbTowns.Items[i];
end;
end;

procedure TForm1.sgWeightsSetEditText(Sender: TObject; ACol, ARow: Integer;
const Value: String); //При изменении ячейки таблицы, вставляем то же значение в симметричную ячейку

begin
// делаем матрицу симметричной принудительно
sgWeights.Cells[ARow,ACol] := Value;
end;

procedure TForm1.btnGenerateClick(Sender: TObject); //Сгенерировать расстояния между городамислучайным образом
var
i, j: integer;
flag: real; // существует ли путь
begin
ClearGrid;
for i:=1 to sgWeights.ColCount-1 do begin

sgWeights.Cells[i,i] := '0';
for j:=i+1 to sgWeights.RowCount-1 do begin

flag := random;
if (flag>0.5) then begin

sgWeights.Cells[i,j] := IntToStr(random(MAXPATH));
sgWeights.Cells[j,i] := sgWeights.Cells[i,j];
end;
end;
end;
end;

procedure TForm1.ClearGrid; //Очистить интерфейсную таблицу расстояний между городами

var
i, j: integer;

begin
for i:=1 to sgWeights.RowCount-1 do
for j:=1 to sgWeights.ColCount-1 do

sgWeights.Cells[i,j] := '';
end;

procedure TForm1.btnClearClick(Sender: TObject); //Очистить список городов
begin
lbTowns.Items.Clear;
end;

[Uli9]

Этой мой код ..алгоритм Дейкстры. Это первая часть работы моего курсовика. Есть ещё вторая. А то что прошу это третья

[Arigato]

Всего 3 города, пользователю нужно попасть из города N в город M через 3-й? Странная задача, тут ни каких даже графов не надо, просто просуммировать расстояния между этими городами и все.

[evg_m]

min(A-C-B)=min(A-C)+min(C-B) ???????????

[Arigato]

А как тут вообще может быть минимальное расстояние? У нас 3 города, хотим попасть из 1-го в 3-й, через 2-й. Считаем длину отрезка, соединяющего 1-й и 2-й город и прибавляем длину отрезка между 2-м и 3-м городом. Или я чего-то не понял в задаче?