bestpath.c

基于二叉树的图最有路径算法

 /*
 *二叉树节点定义
 */
struct binode{
  int lchild;
  int rchild;
  int best;            /*记录最优子路径的节点号int len:记录最优子记录的长度*/
  int length;
}nodes[]={
          0,0,0,0,
          2,3,0,0,
          4,5,0,0,
          6,7,0,0,
          8,5,0,0,
          3,6,0,0,
          9,10,0,0,
          0,11,0,0,
          0,12,0,0,
          0,0,0,0,
          0,7,0,0,
          9,13,0,0,
          2,14,0,0,
          1,3,0,0,
          1,0,0,0
/*有十四个节点:node_num=14*/
 };

/*
 *边的定义
 */
struct edge{
  int pfrom;
  int pto;
  int length;
}edges[]={
           0,0,0,
           1,2,3,
           1,3,4,
           1,5,6,
           1,6,3,
           1,7,55,
           1,10,7,
           1,11,2,
           1,13,34,
           2,3,5,
           2,4,9,
           2,5,54,
           2,6,23,
           2,7,9,
           2,10,13,
           2,11,6,
           2,13,4,
           3,6,76,
           3,7,34,
           3,10,43,
           3,11,75,
           3,13,98,
           4,8,7,
           4,12,76,
           4,14,8,
           5,3,5,
           5,7,65,
           5,11,45,
           5,13,2,
           6,9,23,
           11,9,4,
           12,2,19,
           12,3,34,
           12,5,4,
           12,6,23,
           12,7,9,
           12,10,3,
           12,11,6,
           12,13,9,
           13,1,17,
           13,3,34,
           13,7,9,
           13,11,6,
           14,1,17,
           14,3,34,
           14,7,9,
           14,11,6,
           14,13,23
 };
/*有53条边:edge_num=47*/

/************************
 *顺序栈的操作和结构定义
 ************************/

/*栈的初始化大小*/
#define  MAX_SIZE_SSTACK   20
/*最大长度*/
#define  MAX_LENGTH        9999
/*最多的边数*/
#define MAX_EDGE         60
/*预定义图最大节点个数*/
#define MAX_NODE  20


/*栈元素类型定义*/
typedef  int SElemType;

/*顺序栈的定义*/
typedef struct{
   SElemType data[MAX_SIZE_SSTACK];
   int   poiter;                          /*指示可用栈空间,表示当前栈顶元素位置*/
 }SStack;

/*初始化顺序栈*/
void init(SStack* s)
{
   if(!s)
     {
       printf("\nINIT ERROR!");
       printf("\npress any key to continue!");
       getch();
       exit(0);
      }
   s->poiter=-1;
 }

/*入栈*/
void push(SStack * s,SElemType e)
{
   if(s->poiter<=MAX_SIZE_SSTACK-1)
     s->data[++(s->poiter)]=e;
     else
         {
           printf("PUSH ERROE !Overflow!");
           printf("\npress any key to continue !");
           getch();
           exit(0);
          }
 }
/*出栈，栈空时退出*/
SElemType pop(SStack * s)
{
  if(s->poiter==-1)
    {
      printf("\nPOP ERROR! UNDERFLOW!");
      printf("\npress any key to continue!");
      getch();
      exit(0);
     }
  return s->data[s->poiter--];
 }
/*获取栈顶元素,栈空时返回0*/
SElemType gettop(SStack * s)
{
  if(s->poiter==-1)
    {
       /*printf("\nGETTOP ERROR! UNDERFLOW!");*/
       return 0;                         /*为了协调空栈时stack_flag的取值*/
     }
    return s->data[s->poiter];
 }
/*判空,非空时返回非零数值*/
int empty(SStack * s)
{
   if(s->poiter==-1)
   return 1;
   return 0;
 }

/*************************
 *路径长度查找算法,调用时*
 *返回路径长度,出错返回-1*
 *************************/
 int from_to(int from,int to ,struct edge edges[],int edge_num)
{ /**
   *变量的声明与初始化
   */
  int bottom=1,top=edge_num;              /*上下数组元素号,外层*/
  int p=(int)(1+edge_num)/2;                         /*from的相对概率位置*/
  /**
   *定位from
   */
  while(edges[p].pfrom!=from)
    {
      if(edges[p].pfrom>from)
        {
          top=p;
          p=bottom+(int)((p-bottom)/2);
         }
         else
          {
            bottom=p;
            p=bottom+(int)((top-p)/2);
           }
     }
  while(edges[p].pto>to)
    p--;
  while(edges[p].pto<to)
    p++;
  if(edges[p].pfrom==from&&edges[p].pto==to)
  return edges[p].length;
  printf("\nfrom_to() error! press any key to continue!");
  return;
 }



/*********************
 *两点间最短路径算法 *
 *********************/
void  path(int begin,int end,
           struct binode nodes[],int node_num,
           struct edge edges[],int edge_num)
/**
 *begin and end :开始节点和目的节点；
 *nodes:节点结构体数组；node_num:节点数
 *edges:边结构体数组；edge_num：边数
 */
{
  /*定义变量*/
  int i;                             /*循环变量*/
  int pnode[MAX_NODE+1];             /*标识入栈节点,入栈标识，出栈清零*/
  SStack s_root;                     /*根路径*/
  SStack s_right;
  int now;                           /*当前节点*/

  /*合法节点判断*/
  if((end<1)||(begin<1)||(end==begin)||end>node_num||begin>node_num)
    {
      printf("\nUNDERFLOW OR OVERFLOW ERROR!\npress any ke to contine!");
      return;
     }
  if(nodes[begin].lchild==0)
   {
      printf("\nERROR!NO LEFT CHILD\npress any ke to contine!");
      return;
    }

  /*初始化*/
  for(i=0;i<=node_num;i++)
    {
      pnode[i]=0;                   /*入栈节点*/
      nodes[i].best=0;              /*记录最优子路径根节点*/
      nodes[i].length=MAX_LENGTH;   /*最大长度*/
     }
  nodes[end].length=0;
  nodes[end].best=end;

  init(&s_right);
  init(&s_root);                     /*初始化顺序栈*/
  push(&s_root,begin);               /*开始节点入栈*/
  printf("\npush node %d",begin);
  pnode[begin]=begin;
  pnode[end]=end;
  printf("\n pnode[%d]",begin);
  printf("\n pnode[%d]",end);
  now=nodes[begin].lchild;
  pnode[now]=now;
  printf("\n pnode[%d]",now);

  nodes[begin].lchild=0;
  nodes[end].lchild=0;

  if(now==end)
    {
      nodes[begin].best=end;
      nodes[begin].length=from_to(begin,end,edges,edge_num);
      if(nodes[now].rchild!=0)
        {
          int i;
          i=now;
          now=nodes[now].rchild;
          nodes[i].rchild=0;
          pnode[now]=now;
          printf("\n pnode[%d]",now);
         }
        else
          {
            printf("best path :%d to %d ,length: %d",begin,end,nodes[gettop(&s_root)].length);
            printf("\npress any key to continue!");
            return;
           }
     }
  /*最优路径算法主体*/
  i=0;
  while(now!=begin)
  { /*寻找新的end*/

    if(nodes[now].lchild!=0&&pnode[nodes[now].lchild]!= nodes[now].lchild&&nodes[nodes[now].lchild].best==0)
      {  /*存在左子树（可连接），且当前不在栈中（非最优），（不在栈中）:可下行*/
         int i=now;
         push(&s_root,now);
         now=nodes[now].lchild;
         nodes[i].lchild=0;
         pnode[now]= now;
       }
       else if(nodes[now].lchild==end||nodes[now].lchild!=0&&pnode[nodes[now].lchild]!= nodes[now].lchild)
         {  /*左子树是end，或存在左子树（可连接），且有可行路径（最优，一定不在栈中）：有最优*/
            if(nodes[now].length>(nodes[nodes[now].lchild].length+from_to(now,nodes[now].lchild,edges,edge_num)))
              { nodes[now].best=nodes[now].lchild;
                nodes[now].length=nodes[nodes[now].lchild].length+from_to(now,nodes[now].lchild,edges,edge_num);
               }
            nodes[now].lchild=0;   /*断开与左孩子的连接*/
            /*向上传递*/
            if(nodes[gettop(&s_root)].length>(nodes[now].length+from_to(gettop(&s_root),now,edges,edge_num)))
              {
                 nodes[gettop(&s_root)].best=now;
                 nodes[gettop(&s_root)].length=nodes[now].length+from_to(gettop(&s_root),now,edges,edge_num);
               }
          }
          else if(nodes[now].rchild!=0&&pnode[nodes[now].rchild]!= nodes[now].rchild&&nodes[nodes[now].rchild].best==0)
            { /*存在右子树，且未压栈：可简单的下行*/  
               push(&s_right,now);
               now=nodes[now].rchild;
               pnode[now]= now;
              }
             else if(nodes[now].rchild==end||nodes[now].rchild!=0&&pnode[nodes[now].rchild]!= nodes[now].rchild)
               { /*右子树等于end，或存在右子树，但有可行路径：有最优*/
                 if(nodes[gettop(&s_root)].length>nodes[nodes[now].rchild].length+from_to(gettop(&s_root),nodes[now].rchild,edges,edge_num))
                   {
                     nodes[gettop(&s_root)].length=nodes[nodes[now].rchild].length+from_to(gettop(&s_root),nodes[now].rchild,edges,edge_num);
                     nodes[gettop(&s_root)].best=nodes[now].rchild;
                    }   
                 push(&s_right,now);
                 now=nodes[now].rchild;
                 pnode[now]=now;
                }
                else
                  { /*左右子树都不存在、或没有可行路径、或压栈了,单纯的退栈操作*/
                    int i=now;
                    while(nodes[gettop(&s_right)].rchild==i)
                      {
                        i=pop(&s_right);
                        pnode[i]=0;
                       }
                    if(nodes[now].best!=0&&nodes[gettop(&s_root)].length>nodes[now].length+from_to(gettop(&s_root),now,edges,edge_num))
                      {/*当前节点第一次便是，还没有上传最优路径*/
                        nodes[gettop(&s_root)].best=now;
                        nodes[gettop(&s_root)].length=nodes[now].length+from_to(gettop(&s_root),now,edges,edge_num);
                       }
                    pnode[now]=0;
                    now=pop(&s_root);
                    if(now!=begin&&(nodes[gettop(&s_root)].length>nodes[now].length+from_to(gettop(&s_root),now,edges,edge_num)))
                      {
                         nodes[gettop(&s_root)].length=nodes[now].length+from_to(gettop(&s_root),now,edges,edge_num);
                         nodes[gettop(&s_root)].best=now;
                       }
                   }
   }
  /*输出最优路径*/
  printf("\nthe shortest path from %d to %d is: %d",begin,end,nodes[begin].length);
  printf("\nthe path:");
  printf("\n%d-->",now);
  while(nodes[now].best!=0&&nodes[now].best!=end)
  {
    now=nodes[now].best;
    printf("\n");
    printf("\n%d-->",now);
   }
  printf("\n-->%d",end);
 }

#include<stdio.h>
#include<time.h>
struct tm mytime1;
struct tm mytiem2;
void main(int argc,char* argv)
{
    path(1,10,nodes,14,edges,47);
    printf("\nIN MIAN");
    getch();
 }