Поиск расстояния между двумя точками

[owl1n]

Имеются несколько точек, соединенных между собой, имеется их список, координаты, следовательно и их длина тоже имеется, т.е. выходит взвешенный граф. Но уже второй день не могу понять, как же найти кротчайший путь. Может подскажите? В алгоритме Дейкстры, A* и волновом так и не разобрался

[Luuzuk]

Увы, без дейкстры ничего путного скорее всего не выйдет, придется разбираться

Пара быстро нагугленных реализаций (не проверял):
http://www.codeproject.com/Articles/...ra-s-Algorithm
http://www.codeproject.com/Articles/...stra-Algorithm
http://blog.nerdbank.net/2006/01/c-d...mentation.html

[owl1n]

Сообщение от Luuzuk

Увы, без дейкстры ничего путного скорее всего не выйдет, придется разбираться

Пара быстро нагугленных реализаций (не проверял):
http://www.codeproject.com/Articles/...ra-s-Algorithm
http://www.codeproject.com/Articles/...stra-Algorithm
http://blog.nerdbank.net/2006/01/c-d...mentation.html

Эх, придется заниматься этим "фу", ну хорошо, все равно спасибо, хоть я и натыкался на эти ссылки, все же попробую одну реализацию тут

А можете разъяснить эту реализацию http://www.codeproject.com/Articles/...stra-Algorithm Где тут вводить от куда и до куда искать?

[Luuzuk]

Эта реализация на C++, а не на C#. Она вам точно подойдет?)

[owl1n]

Сообщение от Luuzuk

Эта реализация на C++, а не на C#. Она вам точно подойдет?)

Ой, не ту ссылку дал, по самой первой короче, которую вы давали)

[owl1n]

Ну что? Подскажет еще кто?

[GetMax]

А что вам подсказать то? На входе у нас граф, представленный матрицей смежности. То есть описываете матрицу и заполняете её расстояниями между точками. Например

int [,] matrix = new int[9,9];
matrix[1, 3] = 5; //расстояние между точками 1 и 3 равно 5

Если какие то вершины не соединены между собой, то в матрицу пишете -1(минус один). Ну а дальше по алгоритму, представленному в ссылках.
На выходе получите вектор - пройденные точки. Выводите его и получаете оптимальный маршрут.

[owl1n]

Сообщение от GetMax

А что вам подсказать то? На входе у нас граф, представленный матрицей смежности. То есть описываете матрицу и заполняете её расстояниями между точками. Например

int [,] matrix = new int[9,9];
matrix[1, 3] = 5; //расстояние между точками 1 и 3 равно 5

Если какие то вершины не соединены между собой, то в матрицу пишете -1(минус один). Ну а дальше по алгоритму, представленному в ссылках.
На выходе получите вектор - пройденные точки. Выводите его и получаете оптимальный маршрут.

Я как бы это понял, но он будет искать абсолютно по каждым точкам? Т.е. от 1 до 2, потом от 1 до 3 и т.д.?

[Luuzuk]

ТС, могу предложить вам свой очень старый код (Delphi), который реализует требуемую вам функциональность.
Перевод с Delphi на C# не должен доставить вам особых проблем

{ Функция вернет "Расстояние" между точками a и b ненаправленного графа. 
  Если пути между точками a и b не существует, то функция вернет -1. }
Function GetShortWay(a,b: integer):real;
Var
   D,DW : array of real;
   i,n,j: integer;
   v1,v2: integer;
   index: integer;
   minim: real;
Const M=99999;
begin
  v1:=min(a,b);
  v2:=max(a,b);
  If v1=v2 then
  begin
    Result:=0;
    exit;
  end;
  n:=graph.VertexCount-1;  // в n должно содержаться количество вершин графа минус один
  SetLength(d,graph.VertexCount);  // VertexCount = количество вершин графа
  SetLength(dw,graph.VertexCount);
  
  
  { Вот здесь я пересчитывал матрицу весов.
    Матрица весов выглядит так:
	Двумерный массив (таблица) N на N, где N - количество вершин графа
	На пересечении столбца a и строки b находится "вес" ребра, соединяющего их.
	Если веса рёбер неизвестны, то вес ребра следует принять за единицу
	Если между точками a и b нет прямой связи, то вес считаем равным 99999.
	Название матрицы весов - EdgesWeight (глобальная переменная  EdgesWeight: array of array of real; )
  }
  RebuildWeightMatrix; // Эта процедура описана в комментарии выше
  
  for i := 0 to N do D[i] := EdgesWeight[v1,i];
  for i := 0 to N do DW[i] := 0;
  for i := 0 to N do
  begin
    minim := M;
    index := -1;
    for j := 0 to N do
    if (minim > D[j]) and (DW[j] = 0) then
    begin
      minim := D[j];
      index := j;
    end;
    DW[index] := minim;
    D[index] := M;
    for j := 0 to N do
    begin
      If index<>-1 then
      begin
       if (DW[j] = 0) then D[j] := Min(D[j],DW[index]+EdgesWeight[index,j])
      end else
      begin
        DW[j]:=-1;
        break;
      end;
    end;
  end;
  If dw[v2]=0 then dw[v2]:=-1;
  Result:=DW[v2];
end;





{ Пример использования функции }
procedure Tmain.N15Click(Sender: TObject);
var s: string;
   v1,v2: integer;
   Way: real;
begin
  Try
    Screen.Cursor:=crHourGlass;
    s:=Trim(InputBox('Ввод вершин','Введите номера двух вершин через пробел',''));
    If s='' then exit;
    v1:=StrToInt(Copy(s,1,pos(' ',s)-1))-1;
    Delete(s,1,pos(' ',s));
    v2:=StrToInt(Copy(s,1,Length(s)))-1;
  Except
    Screen.Cursor:=crDefault;
    MessageDlg('Введены некорректные данные, попробуйте ещё раз',mtError,[mbOk],0);
    Exit;
  end;
  If s='' then exit;
  If ((v1<0)or(v1>Graph.VertexCount-1))OR((v2<0)or(v2>Graph.VertexCount-1)) then
  begin
    Screen.Cursor:=crDefault;
    MessageDlg('Указана несуществующая вершина!',mtError,[mbOk],0);
    Exit;
  end;
  Way:=GetShortWay(v1,v2);
  Screen.Cursor:=crDefault; 
  If way=-1 then
  begin
    MessageDlg(Format('Путь из вершины %d в вершину %d не существует.',[v1+1,v2+1]),mtInformation,[mbOk],0);
    Main.pnResult.Caption:=Format('Путь из вершины %d в вершину %d не существует.',[v1+1,v2+1]);
  end
  else
  begin
    MessageDlg(Format('Кратчайший путь между %d и %d вершинами равен %d',[v1+1,v2+1,Round(Way)]),mtInformation,[mbOk],0);
    Main.pnResult.Caption:=Format('Кратчайший путь между %d и %d вершинами равен %d',[v1+1,v2+1,Round(Way)]);
  end;
  Repaint;
end;