求一个寻路算法.

Question

本帖最后由 kaixindzl 于 2011-10-19 18:30:30 编辑

Answer 1

最短路径算法书上网上有一堆,我早忘了(实际开发中用不到啊)
网上可搜下,不过大部分是C的,改成delphi应该不难的
这个有详细说明及C程序,供参考
http://www.cppblog.com/tanky-woo/archive/2011/01/19/138855.aspx

Answer 2

http://topic.csdn.net/u/20111019/17/035a68bf-cb14-4649-bbda-68793881bf9e.html?29020

Answer 3

...procedure TForm1.Button1Click(Sender: TObject);
const max=10000;
var
  gLJJZ:array of array of Integer;//图的邻接矩阵,权值默认都是1
  sList,sFGList:TStringList;
  i,j,n,iR:Integer;
  sRowNum,sNodes:string;
  first,tail,u,min,y,m:Integer;
  dist,path,p:array of Integer;
  s:set of Byte;
begin
  edit1.Text:='1';
  edit2.Text:='13';
  edit3.Text:='';(*
    JD.txt文件内容,第一行表示结点数目
15
1=2,4,7
2=1,3,4,5
3=2,5,8
4=1,2,6,7,11
5=2,3,6,8,9
6=4,5,9,10
7=1,4,11
8=3,5,9,12
9=5,6,8,10,12,13
10=6,9,11,13,14
11=4,7,10,15
12=8,9,13
13=9,10,12,14
14=10,13,15
15=11,14
*)  sList:=TStringList.Create;
  try
    sList.LoadFromFile('.\JD.txt');
    if sList.Count<=0 then exit;
    n:=StrToInt(sList[0]);//结点数目
    SetLength(gLJJZ,n+1,n+1);
    for i:=0 to n do
      for j:=0 to n do
        gLJJZ[i,j]:=max;    sFGList:=TStringList.Create;
    try
      for i:=1 to sList.Count-1 do
      begin
        sRowNum:=sList.Names[i];
        iR:=StrToInt(sRowNum);
        sNodes:=sList.Values[sRowNum];
        sFGList.Delimiter:=',';
        sFGList.DelimitedText:=sNodes;
        for j:=0 to sFGList.Count-1 do
          gLJJZ[iR,StrToInt(sFGList[j])]:=1;//权值都是1
      end;
    finally
      sFGList.Free;
    end;
  finally
    sList.Free;
  end;  first:=StrToInt(edit1.Text);
  tail:=StrToInt(edit2.Text);
  SetLength(dist,n+1);
  SetLength(path,n+1);
  SetLength(p,n+1);  for i:=1 to n do
    dist[i]:=max;  dist[first]:=0;  u:=first;
  s:=[first];
  while u<>tail do
  begin
    for j:=1 to n do
      if not (j in s) and (dist[u]+gLJJZ[u,j]<dist[j]) then
      begin
        dist[j]:=dist[u]+gLJJZ[u,j];
        path[j]:=u;
      end;
      min:=max;
      for j:=1 to n do
        if not (j in s) and (dist[j]<min) then
        begin
          u:=j;
          min:=dist[j];
        end;      if min=max then
      begin
        showmessage('No Answer');
        exit;
      end;      s:=s+[u];
  end;  y:=tail;
  m:=0;
  while y<>first do
  begin
    inc(m);
    p[m]:=y;
    y:=path[y];
  end;  sNodes:=inttostr(first)+' ';
  for j:=m downto 1 do
    sNodes:=sNodes+' '+IntToStr(p[j]);  edit3.Text:=sNodes;  SetLength(dist,0);
  SetLength(path,0);
  SetLength(p,0);
  SetLength(gLJJZ,0);
end;