寻路算法

求一个寻路算法.
如下图:  

例如: 求节点1到节点13的最近路线(经过的节点不能重复, 相同的最近线路任取一条就可以了), 计算出经过的所有节点.  

大家有什么好的算法? 递归? 说说您的思路, 最好斌上您的示例代码, 谢谢!

可能是个菜鸟问题, 要拍砖的同志像我瞄准吧. 





[解决办法]

探讨

书上有专门的算法。

[解决办法]
http://topic.csdn.net/u/20111019/17/035a68bf-cb14-4649-bbda-68793881bf9e.html?29020
[解决办法]
...

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;
[解决办法]
就是图的广度优先遍历树，起点为树根，树枝遇到终点结束。

查看更多 下一篇