图的最短路径算法

作者在 2006-06-03 19:36:00 发布以下内容

今天老师讲了图搜索算法,搞的我一头模糊,什么也听不懂.白白浪费了许多时间.现在我把这个程序放在这如果你会的话指导我一下啊.谢谢了

#include <stdio.h>
#include <math.h>

#define BOOL int
#define TRUE 1
#define FALSE 0
#define MAXN  80
struct node
{
 int row;
        int col;
 struct node * parent;
 struct node * next;
 double g_value;
 double f_value;
};
struct node *close, *open,*goal;

int m, n;
int succeed=0;
int map[MAXN][MAXN];


double heuristic( struct node *x)
{
  /* 计算启发函数 */
  double value;
  value=(m-x->row)*(m-x->row)+(n-x->col)*(n-x->col);
  value=sqrt(value);
  return value;
}
BOOL pass(int x0, int y0, int x1, int y1)
{
 int x,y;
 int bef;
 if ((x0==x1)||(y0==y1))
  return TRUE;   /*若在边上,则可通过*/
 for(x=x0+1; x<=x1; ++x)
 { 
  y=(x-x0)*(y1-y0)/(x1-x0)+y0;
        if ((x-x0)*(y1-y0)%(x1-x0)!=0) y=y+1;
        bef=(x-1-x0)*(y1-y0)/(x1-x0)+y0+1;
  for (int j=bef; j<=y;++j)
      if (map[x][j]) return FALSE;
 }
 return TRUE;

}

void search(struct node *x)
{
 /*
    将新扩展结点放入OPEN表中恰当位置,
    该算法启发函数满足单调性,故不会出现重复扩展问题.

*/
  struct node *p,*q;
 if (open==NULL)
 {
  open=x;
  x->next=NULL;
     return;
 }
 if (open->f_value>=x->f_value)
 {
   x->next=open;
     open=x;
     p=x->next;
     q=x;
 }
 else
 {
  p=open;
  q=p;
  while ((p!=NULL) && (p->f_value<x->f_value))
  {
   /*查找有比x值小的相同结点*/
    if ((p->row==x->row)&&(p->col==x->col))
    {
     delete   x;
     return;
    }
     q=p;
     p=p->next;
  }     
 
  x->next=p;
  q->next=x;
     q=x;
 }
   /*继续查找有无与x相同的节点,有则删除该节点*/
   while (p!=NULL)
   {
       if ((p->row==x->row)&&(p->col==x->col))
    {
     q->next=p->next;
     delete  p;
     return;
    }
    q=p;
    p=p->next; 
  
   }
}


void expend( )
{
 /*从OPEN表中选取第一个结点进行扩展*/
  
 struct node *p,*q;
 while ((open!=NULL)&& (succeed==0))
 {
        p=open;
  open=open->next;
  p->next=close;
  close=p;
      
  /*测试是否是目标状态*/
  if ((p->row==m)&&(p->col==n))
  {
   succeed=1;
      goal=p;
  }
  else
          /*对该节点进行扩展*/
      for (int i=p->row;i<=m;++i)
  

c++practice | 阅读 10814 次
文章评论,共0条
游客请输入验证码