求最佳路径算法问题

平面上已知起始点A位置和终了点B位置  
它们之间存在若干障碍（位置）  
求取一条由A到B的最短安全路径  
(没有具体方案，给点提示或思路也行，我现在已经毫无方向呢)  
---------------------------------------------------------------  
 
看看算法方面的书，多的是实现方法  
---------------------------------------------------------------  
 
应该和Dijkstra得单源最短路径发相近吧。A和B就相当于两个顶点。枝江得若干障碍也看成顶点，障碍之间得之间联系路径长度设为无穷。有Dijkstra算法试一下。  
---------------------------------------------------------------  
 
看看a*算法  
---------------------------------------------------------------  
 
BOOL  CAdjWDigraph::ShortestPaths(int  s  ,double  d[],int  p[])  
{  
            
           BOOL  bsuccess=TRUE;  
           if(s<1    &brvbar;  &brvbar;  s>m_nVertices)  
                       return  FALSE;  
           CChain  L;  
           CChainIterator  I;  
           for(int  i=1;i<=m_nVertices;i++)  
           {  
                       d=array[s];  
                       if(d==NoEdge)  
                                   p=0;  
                       else  
                       {  
                                   p=s;  
                                   L.Insert(0,i);  
                       }  
           }  
           while(!L.IsEmpty())  
           {  
                       int  *v=I.Initialize(L);  
                       int  *w=I.Next();  
                       while(w)  
                       {  
                                   if(d[*w]<d[*v])  
                                               v=w;  
                                   w=I.Next();  
                       }  
                        
                       int  i=*v;  
                       L.Delete(*v);//temp  is  no  use  
                       for(int  j=1;j<=m_nVertices;j++)  
                       {  
                                   if(array[j]!=NoEdge  &&  (!p[j]    &brvbar;  &brvbar;  d[j]>d+array[j]  )  )  
                                   {  
                                               d[j]=d+array[j];  
                                               if(!p[j])  
                                                           L.Insert(0,j);  
                                               p[j]=i;  
                                   }  
                       }  
           }  
           return  bsuccess;  
}  
---------------------------------------------------------------  
 
一本书上的原码，书名忘了:(  
CChain是连表类  
CChainIterator  是个便利器返回CChain的第一个元素，  
算法是D,,,jk.什么算法，具体名字忘了  
我刚用过，没有问题的！  
在数据结构专家门诊里有这类似的问题，其中就有我的，呵呵  
希望能帮上你  
---------------------------------------------------------------  
 
>>  四种寻路算法并比较　2001-09-06  Kanepeng  
 
　　四种算法是DFS、BFS、Heuristic  DFS、Heuristic  BFS  (A*)。用了两张障碍表，一张是典型的迷宫：  
　　char  Block[SY][SX]=  
　　{{1,1,1,1,1,1,1,1,1,1,1  },  
　　  {1,0,1,0,1,0,0,0,0,0,1  },  
　　  {1,0,1,0,0,0,1,0,1,1,1  },  
　　  {1,0,0,0,1,0,1,0,0,0,1  },  
　　  {1,0,1,1,0,0,1,0,0,1,1  },  
　　  {1,0,1,0,1,1,0,1,0,0,1  },  
　　  {1,0,0,0,0,0,0,0,1,0,1  },  
　　  {1,0,1,0,1,0,1,0,1,0,1  },  
　　  {1,0,0,1,0,0,1,0,1,0,1  },  
　　  {1,1,1,1,1,1,1,1,1,1,1  }};  
 
　　第二张是删掉一些障碍后的：  
　　char  Block[SY][SX]=  
　　{{1,1,1,1,1,1,1,1,1,1,1  },  
　　  {1,0,1,0,1,0,0,0,0,0,1  },  
　　  {1,0,1,0,0,0,1,0,1,1,1  },  
　　  {1,0,0,0,0,0,1,0,0,0,1  },  
　　  {1,0,0,1,0,0,1,0,0,1,1  },  
　　  {1,0,1,0,0,1,0,1,0,0,1  },  
　　  {1,0,0,0,0,0,0,0,1,0,1  },  
　　  {1,0,1,0,0,0,1,0,1,0,1  },  
　　  {1,0,0,1,0,0,1,0,0,0,1  },  
　　  {1,1,1,1,1,1,1,1,1,1,1  }};  
 
　　结果：  
　　尝试节点数  合法节点数  步数  
　　深度优先  416/133  110/43  19/25  
　　广度优先  190/188  48/49  19/15  
　　深度+启发  283/39  82/22  19/19  
　　广度+启发  189/185  48/49  19/15  
 
　　所以可以看出深度+启发是最好的，效率高路径也挺短。A*第一是不真实二是慢三是空间消耗较大。  
　　附：dfs+heu的源程序，bc++  3.1通过  
 
　　#include  
　　#include  
　　#include  
 
　　#define  SX  11  //宽  
　　#define  SY  10  //长  
 
　　int  dx[4]={0,0,-1,1};  //四种移动方向对x和y坐标的影响  
　　int  dy[4]={-1,1,0,0};  
 
　　/*char  Block[SY][SX]=  //障碍表  
　　{{  1,1,1,1,1,1,1,1,1,1,1  },  
　　  {  1,0,1,0,1,0,0,0,0,0,1  },  
　　  {  1,0,1,0,0,0,1,0,1,1,1  },  
　　  {  1,0,0,0,0,0,1,0,0,0,1  },  
　　  {  1,0,0,1,0,0,1,0,0,1,1  },  
　　  {  1,0,1,0,0,1,0,1,0,0,1  },  
　　  {  1,0,0,0,0,0,0,0,1,0,1  },  
　　  {  1,0,1,0,0,0,1,0,1,0,1  },  
　　  {  1,0,0,1,0,0,1,0,0,0,1  },  
　　  {  1,1,1,1,1,1,1,1,1,1,1  }};*/  
 
　　char  Block[SY][SX]=  //障碍表  
　　{{  1,1,1,1,1,1,1,1,1,1,1  },  
　　  {  1,0,1,0,1,0,0,0,0,0,1  },  
　　  {  1,0,1,0,0,0,1,0,1,1,1  },  
　　  {  1,0,0,0,1,0,1,0,0,0,1  },  
　　  {  1,0,1,1,0,0,1,0,0,1,1  },  
　　  {  1,0,1,0,1,1,0,1,0,0,1  },  
　　  {  1,0,0,0,0,0,0,0,1,0,1  },  
　　  {  1,0,1,0,1,0,1,0,1,0,1  },  
　　  {  1,0,0,1,0,0,1,0,1,0,1  },  
　　  {  1,1,1,1,1,1,1,1,1,1,1  }};  
 
　　int  MaxAct=4;  //移动方向总数  
　　char  Table[SY][SX];  //已到过标记  
　　int  Level=-1;  //第几步  
　　int  LevelComplete=0;  //这一步的搜索是否完成  
　　int  AllComplete=0;  //全部搜索是否完成  
　　char  Act[1000];  //每一步的移动方向，搜索1000步，够了吧？  
　　int  x=1,y=1;  //现在的x和y坐标  
　　int  TargetX=9,TargetY=8;  //目标x和y坐标  
　　int  sum1=0,sum2=0;  
 
　　void  Test(  );  
　　void  Back(  );  
　　int  ActOK(  );  
　　int  GetNextAct(  );  
 
　　void  main(  )  
　　{  
　　　　memset(Act,0,sizeof(Act));  //清零  
　　　　memset(Table,0,sizeof(Table));  
　　　　Table[y][x]=1;  //做已到过标记  
　　　　while  (!AllComplete)  //是否全部搜索完  
　　　　{  
　　　　　　Level++;LevelComplete=0;  //搜索下一步  
　　　　　　while  (!LevelComplete)  
　　　　　　{  
　　　　　　　　Act[Level]=GetNextAct(  );  //改变移动方向  
　　　　　　　　if  (Act[Level]<=MaxAct)  
　　　　　　　　sum1++;  
　　　　　　　　if  (ActOK(  ))  //移动方向是否合理  
　　　　　　　　{  
　　　　　　　　　　sum2++;  
　　　　　　　　　　Test(  );  //测试是否已到目标  
　　　　　　　　　　LevelComplete=1;  //该步搜索完成  
　　　　　　　　}  
　　　　　　　　else  
　　　　　　　　{  
　　　　　　　　　　if  (Act[Level]>MaxAct)  //已搜索完所有方向  
　　　　　　　　　　　　Back(  );  //回上一步  
　　　　　　　　　　if  (Level<0)  //全部搜索完仍无结果  
　　　　　　　　　　　　LevelComplete=AllComplete=1;  //退出  
　　　　　　　　}  
　　　　　　}  
　　　　}  
　　}  
 
　　void  Test(  )  
　　{  
　　　　if  ((x==TargetX)&&(y==TargetY))  //已到目标  
　　　　{  
　　　　　　for  (int  i=0;i<=Level;i++)  
　　　　　　printf("%d  ",(int)Act);  //输出结果  
　　　　　　printf("%d  %d  %d  ",  Level+1,sum1,  sum2);  
　　　　　　LevelComplete=AllComplete=1;  //完成搜索  
　　　　}  
　　}  
 
　　int  ActOK(  )  
　　{  
　　　　int  tx=x+dx[Act[Level]-1];  //将到点的x坐标  
　　　　int  ty=y+dy[Act[Level]-1];  //将到点的y坐标  
　　　　if  (Act[Level]>MaxAct)  //方向错误？  
　　　　　　return  0;  
　　　　if  ((tx>=SX)  &brvbar;  &brvbar;(tx<0))  //x坐标出界？  
　　　　　　return  0;  
　　　　if  ((ty>=SY)  &brvbar;  &brvbar;(ty<0))  //y坐标出界？  
　　　　　　return  0;  
　　　　if  (Table[ty][tx]==1)  //已到过？  
　　　　　　return  0;  
　　　　if  (Block[ty][tx]==1)  //有障碍？  
　　　　　　return  0;  
　　　　x=tx;  
　　　　y=ty;  //移动  
　　　　Table[y][x]=1;  //做已到过标记  
　　　　return  1;  
　　}  
 
　　void  Back(  )  
　　{  
　　　　x-=dx[Act[Level-1]-1];  
　　　　y-=dy[Act[Level-1]-1];  //退回原来的点  
　　　　Table[y][x]=0;  //清除已到过标记  
　　　　Act[Level]=0;  //清除方向  
　　　　Level--;  //回上一层  
　　}  
 
　　int  GetNextAct(  )  //找到下一个移动方向。这一段程序有些乱，  
　　//仔细看!  
　　{  
　　　　int  dis[4];  
　　　　int  order[4];  
　　　　int  t=32767;  
　　　　int  tt=2;  
　　　　for  (int  i=0;i<4;i++)  
　　　　　　dis=abs(x+dx-TargetX)+abs(y+dy-TargetY);  
　　　　　　for  (i=0;i<4;i++)  
　　　　　　if  (dis<  T)  
　　　　　　{  
　　　　　　　　order[0]=i+1;  
　　　　　　　　t=dis;  
　　　　　　}  
　　　　　　if  (Act[Level]==0)  
　　　　　　　　return  order[0];  
　　　　　　order[1]=-1;  
　　　　　　for  (i=0;i<4;i++)  
　　　　　　　　if  ((dis==t)&&(i!=(order[0]-1)))  
　　　　　　　　{  
　　　　　　　　　　order[1]=i+1;  
　　　　　　　　　　break;  
　　　　　　　　}  
　　　　　　　　if  (order[1]!=-1)  
　　　　　　　　{  
　　　　　　　　　　for  (i=0;i<4;i++)  
　　　　　　　　　　　　if  (dis!=t)  
　　　　　　　　　　　　{  
　　　　　　　　　　　　　　order[tt]=i+1;  
　　　　　　　　　　　　　　tt++;  
　　　　　　　　　　　　}  
　　　　　　　　}  
　　　　　　　　else  
　　　　　　　　{  
　　　　　　　　　　for  (i=0;i<4;i++)  
　　　　　　　　　　　　if  (dis!=t)  
　　　　　　　　　　　　{  
　　　　　　　　　　　　　　order[tt-1]=i+1;  
　　　　　　　　　　　　　　tt++;  
　　　　　　　　　　　　}  
　　　　　　　　}  
　　　　　　　　if  (Act[Level]==order[0])  
　　　　　　　　　　return  order[1];  
　　　　　　　　if  (Act[Level]==order[1])  
　　　　　　　　　　return  order[2];  
　　　　　　　　if  (Act[Level]==order[2])  
　　　　　　　　　　return  order[3];  
　　　　　　　　if  (Act[Level]==order[3])  
　　　　　　　　　　return  5;  
　　}  
 
---------------------------------------------------------------  
 
建议你看看有关图的算法，这是图里面一个比较简单的算法

有没vb的呢