Поиск самого дешёвого пути. Волновой алгоритм

[girlbuuuger]

Необходимо написать программу на делфи. Карта местности задаётся пользователем в виде сетки N на N клеток определённого типа. На карте выбирается местоположение двух населённых пунктов. Требуется проложить самую дешёвую дорогу, связывающую эти 2 пункта, если известна стоимость участка дороги на местности каждого типа(лес-10, поле-20, болото-28 и т.п.).
Так и не смогла разобраться в волновом алгоритме. Помогите пожалуйста

[sabbathist]

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

[girlbuuuger]

Спасибо, sabbathist, это как раз то, что нужно, но как реализовать на делфи, я так и не нашла(((

[Z1000000]

Может это подойдет:
http://www.delphisources.ru/pages/so...-algoritm.html

[Utkin]

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

[Grag]

Когда планируется выход номера???

[Chudo4258]

Алгоритм Дейкстры.
Вот когда-то писал.
Тыпа такого надо? или что?
Алгоритм Дейкстра.rar

[girlbuuuger]

всё это оч похоже. Мне нужно сделать вот такую же программу, но чтоб был алгоритм Дейкстры или хотя бы полегче, чем эта

[sabbathist]

Вам нужен точный алгоритм или тот, что используется в играх (например, когда юниты бегают по карте)? Если точный не нужен, то можно использовать вместо Дейкстры алгоритм A* (А-стар).
Дейкстра есть на паскале, позже выложу.

[sabbathist]

const maxv=1000;
maxe=1000000;
inf=maxlongint;
type PEdge=^TEdge;
 TEdge=record
 v: longint;
 w: longint;
 d: longint;
 ne: PEdge;
end;
var g: array [0..maxv+1] of PEdge;
dist: array [0..maxv+1] of longint;
i,j,n,k,m,v1,v2,a,b,w: longint;
t:  PEdge;
p: array [0..maxv+1] of boolean;

procedure addedge(v1,v2,w: longint);
var x: PEdge;
begin
 new(x);
 x^.v:=v2;
 x^.w:=w;
 x^.ne:=g[v1];
 g[v1]:=x;
end;

procedure Dejkstra(v: longint);
var cur,i: longint;
 r: PEdge;
begin
 fillchar(p,sizeof(p),0);
 for i:=1 to maxv do
   dist[i]:=inf;
 cur:=v;
 dist[v]:=0;
 while cur<>0 do begin
   p[cur]:=true;
   r:=g[cur];
   while r<>nil do begin
     if (dist[r^.v]>dist[cur]+r^.w) then
       dist[r^.v]:=dist[cur]+r^.w;
     r:=r^.ne;
   end;
   cur:=0;
   for i:=1 to n do
     if (p[i]=false) and (dist[i]<>inf) and ((dist[i]<dist[cur]) or (cur=0)) then
       cur:=i;
 end;
 dist[v]:=0;
end;
begin
 assign(input,'input.txt');
 assign(output,'output.txt');
 reset(input);
 rewrite(output);
 read(n,m);
 for i:=1 to m do
  begin
    read(v1,v2,w);
    addedge(v1,v2,w);
    addedge(v2,v1,w);
  end;
 read(a,b);
 dejkstra(a);
 writeln(dist[b]);
end.

тут дейкстра и построение графа. Но вам ведь надо строить "особый граф". Где вес ребер будет равен "стоимости клетки". Но это уже за вами