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

[ArtInt]

Делал я этот исходник в своем черновом варианте, а там рисунки были удалены.
Тут два пути:
1. Добавить в мой исходник описание этих Image и label, чтобы он их увидел. то есть замени в моем исходнике строки от type до private из своего исходника.
2. Либо посмотри, что у меня заменено и просто скопируй это в свой исходник.
Либо, если уж неполучится, то выложи свой исходник модуля Unit1.pas, сделаю замену, чтобы не выдавало ошибок.

[Андрос]

Помог пункт 2.Всё вроде работает , но всеровно как-то стремно смотрица,я думал может в этом алгоритме не надо будет смотреть справо налево если а больше б. И ещё некоторые пути совсем стремно выводит. Может так и надо???Всё равно спасибо за огромную работу и активное участие с ТВОЕЙ стороны!!!!
Стремно например из Докшицы в Вилейку, не проще ли сразу Докшицы-вилейка, а то объезжает 3 пункта помимо этих 2х??? Слушай, а если чё можно ли придумать с первым алгоритмом штуку, чтоб города если а больше б выводились не через стрелочку <=, а к примеру через =>, как-бы менялись местами,зеркально чёли???А то согласись стремно как-то получается в отношении путей???Тут выходит как-бы ,что со стрелочкой <= смотрелось прятней,чем так??? А путь из докшицы в ошмяны вообще стремный...А ??? МОж в первом алгоритме лучше пашоманить???Я теперь вообще в растеренности,завтра курсач показывать, а в 2ом алгоритме стремно как-то

[ArtInt]

В первом алгоритме, где поиск по ширине, Там находился кратчайший путь по индексам городов, которые близко.
Во втором алгоритме Дейкстры (учитывается вес графа, то есть километраж), и близость пункта определяется тем сколько до него километров.
Вот например Дотщица - Вилейка(7-2). Если по прямой то 200 километров шпарить. А если в объезд 180 километров (7-6-8-2) посчитай, есть другой путь (7-8-2) там будет 210. Чувствуется разница?
Нарисуй граф и поставь весы. то есть график и километры поставь. Тогда выгода выведенного пути сразу ощитится по километражу.
Если хочешь, можешь поменять как ты сказал "зеркально", для этого можешь закоментировать ProvPosledov, переменной Napravlenie присвоить тот знак который хочешь, а кусок код изменить так:

  While Finish<>0 do
  Begin
//  Form1.Label5.Caption:=Form1.Label5.Caption+Napravlenie+inttostr(Finish);
    Form1.Label5.Caption:=inttostr(Finish)+Napravlenie+Form1.Label5.Caption;
  //  Form1.Label1.Caption:=Form1.Label1.Caption+Napravlenie+Gorod(Finish);
    Form1.Label1.Caption:=Gorod(Finish)+Napravlenie+Form1.Label1.Caption;
    Form1.Label8.Caption:=inttostr(SummaKm);
    Finish:=Path[Finish];
  End; {while}

Чувствуешь разницу при выводе?

Так что здесь два варианта как ты видишь вывода кратчайшего пути, но для автомобилиста я думаю важнее сколько километров надо проехать, ведь от этого зависит расход топлива и время поездки тоже.
Поэтому для таких задач и применяют метод Дейкстры.
В wikipedia читал?

И кстати проверь еще раз матрицу смежности для первого алгоритма, по-моему там где-то ошибка была.

[Андрос]

[QUOTE=ArtInt;

И кстати проверь еще раз матрицу смежности для первого алгоритма, по-моему там где-то ошибка была.[/QUOTE]
Cлушай, смотрел я эту матрицу, и на листике рисовал, но вроде ошибок не увидел,можешь сказать где поточнее???? в строке 7 честно-не вижу.
Вот картинка...А вот док-ент, который одержит расстояния между городов,ПОСМОТРИ,ПЛИЗ,нифига не вижу ошибки

( //1 //2 //3 //4 //5 //6 //7 //8 //9
(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
//1 //2 //3 //4 //5 //6 //7 //8 //9
);
А вот матрица расстояний
mRasstKm:array[1..n,1..n] of integer =
( //1 //2 //3 //4 //5 //6 //7 //8 //9

( 0, 65, 102, 0, 0 , 0, 0, 0, 0), //1
( 65, 0, 54, 0, 0, 0, 67, 91, 0), //2
( 102, 54, 0, 31, 55, 0, 0, 0, 0), //3
( 0, 0, 31, 0, 62, 0, 0, 0, 0), //4
( 0, 0, 55, 62, 0, 56, 0, 68, 0), //5
( 0, 0, 0, 0, 56, 0, 135, 52, 21), //6
( 0 , 70, 0, 0, 0, 135, 0, 104, 118), //7
( 0, 30, 0, 0, 37, 52, 104, 0, 0), //8
( 0, 0, 0, 0, 0, 21, 118, 0, 0) //9
);

И ещё хотелось бы узнать про функцию город
точнее про 1: Result:='Нарочь';
2: Result:='Вилейка';
3: Result:='Сморгонь';
для чего Result, это какое-то зарезерв-ое слово???или как
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, ,,,,,,,,,,,
И еще ,что такое итнрате т.е for I := 1 to 9 do // Iterate, как понимать это слово???
Заранее СПАСИБО!!!

[ArtInt]

Где было 40 а теперь 200 выделено жирным

//протяженность в км между городами, весы графа
   mRasstKm:array[1..n,1..n] of integer =
( //1    //2      //3    //4   //5    //6   //7     //8  //9

 (  0,    89,     120,    0,    0 ,    0,    0,     0,    0),  //1
 ( 89,    0,      30,     0,    0,     0,    200,   60,   0),  //2
 ( 120,   30,     0,     40,    120,   0,    0,     0,    0),  //3
 ( 0,     0,      140,   0,     130,   0,    0,     0,    0),  //4
 ( 0,     0,      120,   130,   0,     100,  0,     110,  0),  //5
 ( 0,     0,      0,     0,     100,   0,    70,    50,   90), //6
 ( 0 ,    200,     0,     0,     0,     70,   0,    150,  80), //7
 ( 0,     60,     0,     0,     110,   50,   150,   0,   0), //8
 ( 0,     0,      0,     0,     0,     90,   80,    0,   0)  //9
);

Проверь, может ты уже исправил это но у меня была такая ошибка

[Андрос]

Дело в том (я решаю по 1у алгоритму), расстояния я поменял, те матрица теперь у меня такая---(расстояний)
mRasstKm:array[1..n,1..n] of integer =
( //1 //2 //3 //4 //5 //6 //7 //8 //9

( 0, 65, 102, 0, 0 , 0, 0, 0, 0), //1
( 65, 0, 54, 0, 0, 0, 67, 91, 0), //2
( 102, 54, 0, 31, 55, 0, 0, 0, 0), //3
( 0, 0, 31, 0, 62, 0, 0, 0, 0), //4
( 0, 0, 55, 62, 0, 56, 0, 68, 0), //5
( 0, 0, 0, 0, 56, 0, 135, 52, 21), //6
( 0 , 70, 0, 0, 0, 135, 0, 104, 118), //7
( 0, 30, 0, 0, 37, 52, 104, 0, 0), //8
( 0, 0, 0, 0, 0, 21, 118, 0, 0) //9
);
В файле я выложил расстояние между всеми пунктами и смотрел по нему.В моём варианте не надо 200???

[ArtInt]

Проверь пути 8-5 и 2-7. Почему то у меня не сходится.
Попробуй Нарисовать граф и написать эти км.

[Андрос]

Слушай, тут так получается у меня выводит то расстояние, которое я ввел в матрице.Ничего не понимаю , попробую скинуть мой юнит 1.пас,
посмотри,плиз, я понял одно---ты скорее всего прав, тока я что-то не допетрил...
и такой вопрос--можно-ли если абольше б то выводило не так воложин<=молодечно=37, а так 37=воложин<=молодечно

[ArtInt]

Сообщение от Андрос

Слушай, тут так получается у меня выводит то расстояние, которое я ввел в матрице.Ничего не понимаю , попробую скинуть мой юнит 1.пас,
посмотри,плиз, я понял одно---ты скорее всего прав, тока я что-то не допетрил...
и такой вопрос--можно-ли если абольше б то выводило не так воложин<=молодечно=37, а так 37=воложин<=молодечно

Вероятнее всего из за неправильной матрицы
Например пусть матрица будет такой
//протяженность в км между городами, весы графа
mRasstKm:array[1..n,1..n] of integer =
( //1 //2 //3 //4 //5 //6 //7 //8 //9

( 0, 65, 102, 0, 0 , 0, 0, 0, 0), //1
( 65, 0, 54, 0, 0, 0, 70, 91, 0), //2
( 102, 54, 0, 31, 55, 0, 0, 0, 0), //3
( 0, 0, 31, 0, 62, 0, 0, 0, 0), //4
( 0, 0, 55, 62, 0, 56, 0, 68, 0), //5
( 0, 0, 0, 0, 56, 0, 135, 52, 21), //6
( 0 , 70, 0, 0, 0, 135, 0, 104, 118), //7
( 0, 91, 0, 0, 68, 52, 104, 0, 0), //8
( 0, 0, 0, 0, 0, 21, 118, 0, 0) //9
);
Вот исправленная матрица, где ошибка жирным

Для вывода килом впереди сделай так
LPutKm.Caption:=inttostr(mRasstKm[first,Second])+'='+Gorod(second)+Napravlenie+Gor od(first)+';'+LPutKm.Caption;

------------------------------///////////////////
Если останется время, попробуй реализовать выделение путей на рисунке. Как примерно это может выглядеть посмотри на прилагаемом рисунке.
Сейчас опишу как это реализовать в твоей программе.
Для начала в создании формы form1.create; вначале пропиши

a:=0; b:=0

Потом добавь в модуль Unit1, процедуру

procedure TForm1.Cvet (index, index2: byte);
begin
 case index of
  1: begin
       CoordX:=143;
       CoordY:=162;
     end;
  2: begin
       CoordX:=196;
       CoordY:=172;
     end;
  3: begin
       CoordX:=108;
       CoordY:=215;
     end;
  4: begin
       CoordX:=77;
       CoordY:=259;
     end;
  5: begin
       CoordX:=136;
       CoordY:=278;
     end;
  6: begin
       CoordX:=184;
       CoordY:=289;
     end;
  7: begin
       CoordX:=244;
       CoordY:=228;
     end;
  8: begin
       CoordX:=180;
       CoordY:=232;
     end;
  9: begin
       CoordX:=254;
       CoordY:=292;
     end;
 end;


  Image2.Canvas.Pen.Color:=clRed;
  Image2.Canvas.Pen.Width:=8;
 // Image2.Canvas.Pen.Style:=psDot;
//  Image2.Canvas.Pen.Mode:=PmMergePenNot;// более менее
// Image2.Canvas.Pen.Mode:=PmMergeNotPen;//тоже пойдет
 Image2.Canvas.Pen.Mode:=pmNotXor;//стирание

  Image2.Canvas.MoveTo(CoordX,CoordY);

 case index2 of
  1: begin
       CoordX:=143;
       CoordY:=162;
     end;
  2: begin
       CoordX:=196;
       CoordY:=172;
     end;
  3: begin
       CoordX:=108;
       CoordY:=215;
     end;
  4: begin
       CoordX:=77;
       CoordY:=259;
     end;
  5: begin
       CoordX:=136;
       CoordY:=278;
     end;
  6: begin
       CoordX:=184;
       CoordY:=289;
     end;
  7: begin
       CoordX:=244;
       CoordY:=228;
     end;
  8: begin
       CoordX:=180;
       CoordY:=232;
     end;
  9: begin
       CoordX:=254;
       CoordY:=292;
     end;
 end;


  Image2.Canvas.LineTo(CoordX,CoordY);

 //   Showmessage(inttostr(CoordX)+'='+inttostr(CoordY));
        //Image2.Canvas.LineTo(CoordX,CoordY);
       //Image2.Canvas.LineTo(110,20);
end;

Не забудь объявить ее в форме.
Введи глобальные переменные

 CoordX, CoordY: integer;

Измени этот кусок кода:

   if sumarray[i]<>0 then
   begin
     first:=sumarray[i];
     second:=sumarray[i+1];
     if (first<>0) and (second<>0) then
     begin
       SummaKm:=mRasstKm[first,Second]+SummaKm;
      // LPutKm.Caption:=Gorod(second)+Napravlenie+Gorod(first)+'='+inttostr(mRasstKm[first,Second])+';'+LPutKm.Caption;
        LPutKm.Caption:=inttostr(mRasstKm[first,Second])+' км'+'='+Gorod(second)+Napravlenie+Gorod(first)+';'+#10#13+LPutKm.Caption;
        Cvet(first,second);
     end;

Добавь следующее в начало кнопки "Показать путь"

procedure TForm1.Button1Click(Sender: TObject);
begin
//стираем старый путь

if (a<>0) and (b<>0) then
 begin
   ProvPosledov(a,b);
  // Showmessage(inttostr(a)+'='+inttostr(b));
 A_to_B(a, b);
 end;

LPutKm.Caption:='';

При повторном вызове прорисовки линии она затирается, потому режим стоит

Image2.Canvas.Pen.Mode:=pmNotXor;//стирание

И самое главное пересохрани рисунок Bu копия.jpg в Bu копия.bmp и загрузи его, иначе возможно будет выдавать ошибку что не может рисовать на данной поверхности.

[ArtInt]

Координаты точек вычислял по нажатию на рисунок

procedure TForm1.Image2MouseDown(Sender: TObject; Button: TMouseButton;
  Shift: TShiftState; X, Y: Integer);
begin
showmessage(inttostr(X)+'-'+inttostr(y));

end;

А потом вставлял их в исходник, если где то линии будут кривые можешь подправить таким образом.