shortestpath.c

多段图的最短路径 c语言实现源代码 可以运行

#include<stdio.h>
#include<malloc.h>
#define MAX_TYPE 3.14E38
#define ZERO_TYPE 0

struct NODE
{
    int v_num;
    float len;
    struct NODE *next;
};



float fgraph (struct NODE node[], int route[], int n,int *number){
 
 int i;
 struct NODE *pnode;
 int path[26];
 float min_cost, cost[26];
 for (i=0;i<n ;i++ )
 {
     cost[i]= MAX_TYPE;
     path[i]=-1;
     route[i]=0;

 }
 cost[n-1]=ZERO_TYPE;
 for (i=n-2;i>=0 ;i-- )
 {
     pnode=node[i].next;
     while (pnode!=NULL)
     {
         if (pnode->len+cost[pnode->v_num]<cost[i])
         {
             cost[i]=pnode->len+ cost[pnode->v_num];
             path[i]=pnode->v_num;
         }
        pnode=pnode->next;
     }
 }

 i=0;
 while ((route[i]!=n-1)&&(path[i]!=-1))
 {
     i++;
     route[i]=path[route[i-1]];
 }
 *number=i+1;
 min_cost =cost[0];
 return min_cost;

}

void main()
{
  struct NODE a[26];struct NODE *head,*q1,*q;
  int p[26];float d[26];
  int n,i,j=0;float min_cost;
  int number;
  int route[26];
  char signal;/*??????*/
  printf("please put in the number n(0-25):\n");
  scanf("%d",&n);getchar();
  printf("n=%d\n",n);
  

  for(i=0;i<n;i++)
  {
      printf("put in the node(0-25):\n");
      scanf("%d",&a[i].v_num); getchar();
      printf("a[i].v_num=%d\n",a[i].v_num);
      q=q1=(struct NODE *)malloc(sizeof(struct NODE));
      j=0;
       do
      { if(j==0);
        else
          printf("please put in the next:\n");
        printf("\n still put in(choose'y'or'n')?\n");
        scanf("%c",&signal);
        if(signal=='n'||signal=='N') break;
        else if(signal=='y'||signal=='Y')
        {
          printf("please put in the still number(two number,v_num:0-25,len:any):\n");
          scanf("%d%f",&(q->v_num),&(q->len));getchar();
          if(j==0) a[i].next=q;
          else
            q1->next=q;/*????*/
          q1=q;
          q=(struct NODE *)malloc(sizeof(struct NODE));
          j++;

        }

        else printf("error!\n");
      }
      while(j<100);
      q1->next=NULL;
  }
  printf("\nthe array a just put in:\n");
  for(i=0;i<n;i++)
    {
      q=a[i].next;
      printf("i=%d,a[%d].v_num=%d,v_len=%f\n",i,i,a[i].v_num,a[i].len);
      printf("i=%d:\n",i);
      while(q!=NULL)
         {printf("v_numnext[%d]=%d,v_len to a[%d].v_num=%f\n",i,q->v_num,i,q->len);q=q->next;}
      printf("\n");
    }
  min_cost=fgraph(a,route,n,&number);
  printf("number=%d\n",number);
  printf("after fgraph the road:\n");
  for(i=0;i<number-1;i++)
  printf("%d->",route[i]);
  printf("%d",route[number-1]);
  printf("\n");
  printf("min_cost=%f",min_cost);
  getchar();
}