多段图.txt

算法分析中的向前算法的实现 输入为 弦数 段数 接点数 几弦的有关信息 输出 最优路径

#include<stdio.h>
#include<stdlib.h>
struct arcnode
{
   int head;
   int len;
   struct arcnode *next;
};
struct vnode
{
  int data;            //顶点编号
  struct arcnode  * firstarc ;//指向第一条依附该顶点弧的指针
 };

void FGRAPH(int E,int k,int n)
{
    int i,temp,* value;
    int *path,*D;
    struct arcnode *s;
    int tail,head,length;
    struct vnode *vnode;
    value=(int*)calloc(n,sizeof (int));
    path=(int*)calloc(k,sizeof (int));
    D=(int*)calloc(n,sizeof (int));
    vnode=(struct vnode*)calloc(n,sizeof (struct vnode));

//***********************************************   
  for(i=1;i<n+1;i++)
    {
      vnode[i].firstarc=NULL;
      vnode[i].data=i;
     }
    printf("input arc info:tail. head. len :\n");
    for(i=1;i<=E;i++)
   {
      scanf("%d,%d,%d",&tail,&head,&length);
      s=(struct arcnode*)malloc(sizeof(struct arcnode));
      s->head=head;
      s->len=length;
      s->next=vnode[tail].firstarc;
      vnode[tail].firstarc=s;
    }
//*******************************************创建邻接表

for(i=1;i<=n;i++)
    value[i]=0;
   for(i=n-1;i>=1;i--)
   {
      s=vnode[i].firstarc;
      value[i]=s->len+value[s->head];
      D[i]=s->head;
      s=s->next;
      while(s)
      {
	 temp=s->len+value[s->head];
	 if(temp<value[i])
	 {
	    value[i]=temp;
	    D[i]=s->head;
	 }
	 s=s->next;
      }
   }
  path[0]=1;
   path[k-1]=n;
   for(i=1;i<k-1;i++)
   path[i]=D[path[i-1]];
   printf("Path:");
   for(i=0;i<k;i++)
   printf("%d  ",path[i]);
   printf("\nThe value:%d\n",value[1]);
}


void main()
{int E,k,n;
 printf("input arcnum  duanum  nodenum\n");
 scanf("%d",&E);
 scanf("%d",&k);
 scanf("%d",&n);
 FGRAPH(E,k,n);
}