Поиск кротчайшего пути в делфи 7

[Андрос]

Уважаемые модераторы,не удаляйте эту тему.Я понимаю, что сдесь есть похожие, но они мне не помогли.
Моя задача поиск кротчайшего пути в графе(размер (9х9)).С этим я вроде бы справился.,но вот в чем проблемы---
1)Нужно, чтоб когда я выбрал города 1 и 2 из комбобокса и нажал кнопку показать путь, он отображал помимо такого пути 2-4-6-7 ещё в отдельном лэйбле и расстояние общее от города 1 до годода 2 И ПОМИМО этого ещё в отдельной лэйбле пути так(вместо цифр 2-4-6-7 ) он показывал Минск-Молодечно-Вилейка-Гомель.Расстояния нужно чтоб брались из матрицы.При выборе города1 и годода 2 расстояния берутся из матрицы 9х9(где каждому городу соответствует своё рассояние.
Люди,помогите....Плиз, я знаю, что на этом форуме много умных людей..Мне это надо сдать во вторник,ПОМОГИТЕ,ПЛИЗ...
И ЕЩЕ - правильный ли я выбрал алгоритм для работы с поиском кротчайшего пути в графе??????хелп!!!Вот текст проги---

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls, jpeg, ExtCtrls, Buttons, Menus, XPMan, shellapi;
  const
 n = 9;
 m:array[1..n,1..n] of boolean =
(
 (false, true, true, false, false ,false, false, false, false),  //1
 (true, false, true, false, false, false, true, true, false),    //2
 (true, true, false, true, true, false, false, false, false),    //3
 (false, false, true, false, true, false, false, false, false),  //4
 (false, false, true, true, false, true, false, true, false),    //5
 (false, false, false, false, true, false, true, true, true),    //6
 (false ,true, false, false, false, true, false, true, true),    //7
 (false, true, false, false, true, true, true, false, false),    //8
 (false, false, false, false, false, true, true, false, false)    //9
);

type
 matr=array[1..n,1..n] of integer;
  TForm1 = class(TForm)
    Image1: TImage;
    ComboBox1: TComboBox;
    ComboBox2: TComboBox;
    Image2: TImage;
    Label3: TLabel;
  private
   a,b:integer;
   Procedure A_to_B (a,b:integer);
  public
    { Public declarations }
  end;
vфr
  Form1: TForm1;
implementation
uses Unit2
{$R *.dfm}
procedure TForm1.A_to_B(a, b: integer);
var
 visited:array[1..n] of boolean;
 prev:array[1..n] of integer;
 c:array[1..n] of integer;
 head,tail:integer;
 f:boolean;
 i,v,k:integer;
begin
 head:=1;
 tail:=1;
 f:=false;
 for i:=1 to n do
begin
visited[i]:=false;
prev[i]:=0;
end;
 c[tail]:=a;
 visited[a]:=true;
 while (head<=tail) and not f do
begin
   v:=c[head];
   head:=head+1;
   for k:=1 to b do
   if m[v,k] and not visited[k] then
   begin
   tail:=tail+1;
   c[tail]:=k;
   visited[k]:=true;
   prev[k]:=v;
   if k=b then
   begin
   f:=true;
   break;
   end;
   end;
   end;
  if f then
   begin
   k:=b;
   Label1.Caption:= IntToStr(b);
   while prev[k]<>0 do
   begin
   Label1.Caption:= IntToStr(prev[k])+'=>'+Label1.Caption  ;
   k:=prev[k];
   end;
   end
   else
   ShowMessage('Пути из города ' + IntToStr(a) + ' в город ' + IntToStr(b) + ' необнаруженно т.к идет ремонт дорог, либо движение в заданном направлении закрыто).');
   end;


procedure TForm1.Button1Click(Sender: TObject);
var
i:integer;
s,d,f,g:string;
begin
 case ComboBox1.ItemIndex of
  0: a:= 1;
  1: a:= 2;
  2: a:= 3;
  3: a:= 4;
  4: a:= 5;
  5: a:= 6;
  6: a:= 7;
  7: a:= 8;
  8: a:= 9;
 end;
 case ComboBox2.ItemIndex of
  0: b:= 1;
  1: b:= 2;
  2: b:= 3;
  3: b:= 4;
  4: b:= 5;
  5: b:= 6;
  6: b:= 7;
  7: b:= 8;
  8: b:= 9;
 end;
 A_to_B(a, b);
// if (combobox1.Text='Молодечно') and (combobox2.Text='Минск') then
 //label5.Caption:='80 km';
 s:=label1.Caption;
 g:=label1.Caption;
 f:=label1.Caption;
 d:=label1.Caption;
 i:=length(s);
 for i:=0 to length(s) do
 if s[i]='1' then s:='Минск';
 for i:=0 to length(d) do
 if d[i]='4' then d:='Молодечно';
 for i:=0 to length(f) do
 if f[i]='7' then f:='Мядель';
  label8.Caption:=s+'=>'+d+'=>'+f;
end;

procedure TForm1.FormCreate(Sender: TObject);

begin
//вывод содержимого метки 2
 Label2.Caption:= '1 Минск' + #13 +
  '2 Молодечно' + #13 +
  '3 Вилейка' + #13 +
  '4 Вязань' + #13 +
  '5 Гродно' + #13 +
  '6 Витебск' + #13 +
  '7 Гомель' + #13 +
  '8 Могилев' + #13 +
  '9 Сморгонь';

end;
end.

[Ntlegend]

учися оформлять код тегами (кнопочка #)

вместо

case ComboBox1.ItemIndex of
****
case ComboBox2.ItemIndex of

напиши

a := ComboBox1.ItemIndex+1;
****
b := ComboBox2.ItemIndex+1;

исправь

//вывод содержимого метки 2
Label2.Caption:= '1 Минск' + #13#10 +
'2 Молодечно' + #13#10 +
'3 Вилейка' + #13#10 +
'4 Вязань' + #13#10 +
'5 Гродно' + #13#10 +
'6 Витебск' + #13#10 +
'7 Гомель' + #13#10 +
'8 Могилев' + #13#10 +
'9 Сморгонь';

и еще одно.. я абсолютно не понял шо ты хотел спросить.. и пример твой не компилится (алиасы настраивать я не буду)..

[Андрос]

Суть заключается в том, чтобы при воборе 2х городов и при нажатии кнопки выводились города через которые мы проезжаем включая начальный и конечный город.Например---едем из 2 в 5 и показывается
2-3-4-5.Это я сделал.+Но к этому нужно добавить в отдельный лэйбл вывод названий городов---чтоб вместо 2-выводилось минск, вместо3- вилейка, вместо4-вызынь,и вместо 5 сморгонь,Т.Е так минск-вилейка-вызынь-сморгонь.Далее нужно создать матрицу расстояний-т.е 9х9, где каждому городу соответствует свое расстояние и выводится оно должно в лэйбл тоже при нажатии этой же кнопки.Т,Етдолжно выводится общее расстояние менжду городами(к примеру минск-вилейка-вызынь-сморгонь)
расстояние 500км.помогите!!!!плиз!!!вот исходник(рабочий)---

Предложите свои варианты с расчётом расстояния между городов.Мне должно выводить суммарное--т.е расстояние межде выбраными пунктами К примеру 2-3-4-5 расстояние 300км.Исходник качайте второй(сообщ.2).И ЕЩЁ помогите вот текст проги прокаменти его,а то я не могу найти литературы по данному коду.ОБЪЯСНИТЕ КАЖДУЮ СТОКУ( // И КОМЕНТАРИЙ)плиз!!!!

[ArtInt]

То, что ты просил, я сделал, может не самый элегантный способ, но работает.
Первое для скачки это модернизированный твой исходник,
второе это рисунок графа.
В целом, рекомендую найти книгу Решение олимпиадных задач.
Там такие примеры как решать более оптимально описывается.
Насчет оформления, сделай подобие карты, можешь из реальной вырезать кусок, где города будут реальными и расстояния тоже, найди их гербы, выдели дороги. Только обрати внимание, чтобы рисунок соответствовал твоему графу.
Сделай заставку, описывающую вначале кем создана программа и для чего.
Если время останется до сдачи курсовой попробуй увеличить количество городов.
В принципе, думаю понятно, что там в первом массиве показано есть ли дорога или нет с соседними городами, а Втором массиве(модернизированный исходник) расстояния записаны.

[Андрос]

Всё работает ПРАКТИЧЕСКИ хорошо.Спасибо тебе ArtInt ЗА помощь.Хоть один умный и отзывчивый человек нашёлся.!!!
ЕСть следующие проблемы--Поиск пути из меньшего значения к большему идет нормально(например из 1 в 5 и т.д), но когда я пытаюсь указывать города из 9 в 1, то прога выбивает результат-ГОродов НЕТ,хотя в матрице пути стоят правильно.ПОМОГИТЕ люди, скажите что за хрень. Мне ко вторнику сдавать , а тут такой облом....ПЛИЗ,ХЕЛП!!!!!
И еще , скажи мне ArtInt что означает nomer:=2; Это зачем???
Вот исходник, может кто ещё подскажит по поводу описаной мною проблемы-----

[ArtInt]

nomer:=2;//для того чтобы в массиве sumarray начинать со второго элемента, так как повыше для первого элемента уже присваивали.
Самый простой способ это делать проверку значений a,b и если a>b тогда менять местами, ведь от перемены сумм слагаемых сумма не меняется.
Выкладываю обновленный исходник.

[Андрос]

Про перемену мест это идея хорошая, но препод требовательный и к такому выводу(задом наперед), даебё...ся,может можно чтоб выводило по порядку,а не задом наперед при твоём варианте сравнения???Помоги,плз. препод у нас требовательный,ко вторнику надо сдать....Может есть другой вариант,может добавить ещё 1 матрицу 9х9,содержащую пути,только сравнения будем делать начиная не с 1 ,а с 9.Есль что то вот она, осталось как-то подключить.НО КАК???Или есть другой вар-т???Хелп, плиз!!!!!!!!!
матрица=----
////vtoraya матрица(НЕ ЗНАЮ ЗАЧЕМ, МОЖЕТ НЕ НУЖНА)
vtoraya:array[1..n,1..n] of boolean =
( //1 //2 //3 //4 //5 //6 //7 //8 //9
(false, false, false, false, false, true, true, false, false), //9
(false, true, false, false, true, true, true, false, false),//8
(false, true, false, false, false, true, false, true, true),//7
(false, false, false, false, true, false, true, true, true),//6
(false, false, true, true, false, true, false, true, false),//5
(false, false, true, false, true, false, false, false, false),//4
(true, true, false, true, true, false, false, false, false),//3
(true, false, true, false, false, false, true, true, false),//2
(false, true, true, false, false, false, false, false, false)//1
//1 //2 //3 //4 //5 //6 //7 //8 //9
);

[ArtInt]

Если сделать вторую матрицу, то наверное у него будет еще больше претензей, так как это слишком нецелесообразное расходование памяти.
Насчет, как без перемены мест сделать посмотрю. Чуть попозже выложу исходник.

Почему, кстати преподаватель придерется?
Если посмотреть, то процедура A_to_B(a, b: integer);- это нисходящий проход по значениям и a не должно быть больше b. Там ведь цикл такой стоит, получается что делать два алгоритма, но это ведь нецелесообразно, если можно поступить проще.
Поэтому, может лучше оставить как есть.

Кстати, все остальное в программе реализовал? Там Расчет топлива, вывод отчета? Нормальный рисунок графа. Оформление программы тоже времени немало занимает.
Сделай проверку если название текста в Combobox Начало или Конец, то вывод сообщения "Введите начало пути и окончание".
В целом сделай все по оформлению и другому коду.
Насчет почему введена процедура ProvPosledov(a,b);, то объясни, потому
в процедуре A_to_B реализован нисходящий проход, то есть от меньшего к большему. И легче поменять местами а и b нежели писать процедуру по восходящему проходу, ведь смысл не меняется, что из a в b, что из b в a, все равно расстояние то одинаковое.
Я так понимаю, это ведь предварительная сдача курсовых работ так, не защита курсовой?
Если преподаватель сделает замечание на счет алгоритма, то лучше сразу спросить как он себе представляет другой алгоритм и какую литературу почитать? Или приведет пример.
Возможно будут придирки насчет массивов, так как они занимают память, но с другой стороны у нас всего 9 элементов, а не 100 или 1000,
В другом случае, наверное было бы лучше их размещать в текстовый файл и оттуда считывать по частям.

[Андрос]

Сдача курсового назначена на 4-5 МАЯ.
В принципе курсач готов на 40-45%.Но остаются серьёзные вопросы по поводу---
1)Вывод городов из большего к меньшему должен быть так:Чтоб если а<b стрелочка=> менялась на <=.Т.е к примеру- путь из 9 в 1 паказывался так 1<=2<=7<=9 вместо такого вывода 1=>2=>7=>9
2)Нужно чтоб если не введены какие либо данные в Едиты выводилось сообщение---Нужно заполнить все поля!!!
+ В эдиты далжны вводится только цифры,на буквы 0 реакции.Я понимаю это исключительные ситуации, но реализовать их у меня не получилось-ОШИБКА.
3)Сделать проверку если название текста в Combobox Начало или Конец, то вывод сообщения "Выберете из списка начало пути и его окончание".
А то так выводится пути из 0 в 0 нет,Это точно надо как-то выбрасить.
4)если город а=б, т.е к примеру молодечно-молодечно то выводится сообщение ----Вы в этом городе!!!
+ к этому если городов не найдено---Пути из города(название) в город(название) нет!!!Но это сообщение выдается,тока надо чтоб вместо цифр выводились города.
Расчет топлива будет выглядеть примерно так---на форме 3
Люди помогите вот мой курсач.Может возникнуть проблемы с базами, типу на моем компе работает, а на др нет,может проблемы с элиасами???
ПОМОГИТЕ ,ПЛИЗ, ЗАЩИТА КУРСАЧА ЧЕРЕЗ5 ДНЕЙ ,А У МЕНЯ ПРАКТИЧЕСКИ НИЧЕГО НЕТ.плиз,ХЕЛП,БУДУ РАД ЛЮБОЙ ПОМОЩИ!!!!

[ArtInt]

Все 4 пункта решаются легко, посмотри исходник.
Будет ли работать на другом компе?
Тут мне стало интересно, когда ты сказал, что базы данных используешь,
где?
В исходниках, которые ты разместил они не используются.
алиасы прописываются только для баз данных, если ты используешь BDE, Ado, Interbase или еще что нибудь.
Программа должна работать на другом компьютере, если там конечно Windows стоит, а не чистый Dos или Linux или другая операционная система.
И если не изменял какие нибудь параметры компиляции пакетов (по умолчанию они компилируются в exe).
Так что программа должна работать на другом компе...
И все таки посмотри как оформить интерфейс программы, пока что с пользовательской точки не очень.
Может вторую форму сделать модальной (Form1.ShowModal), да и текст должен быть понаглядней, а то где-то с фоном сливается.
Если есть вопросы пиши...