多段图.cpp

这是在邻接表的基础上实现的多段图的向前算法

#include <iostream.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20    
#define MAX_EDGE_NUM 40   
typedef int VertexType ;      
typedef struct ArcNode
{ 
 int adjvex;
 int weight;
 struct ArcNode *nextarc;
}ArcNode;

typedef struct VNode
{ 
 VertexType data;
 ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct 
{ 
 AdjList vertices;
 int vexnum,arcnum;
}ALGraph;
void CreateDG(ALGraph &G)
{
 int i,j,k,w;
 ArcNode *p;
 cout<<"创建一个图:"<<endl;
 cout<<"顶点数:";
 cin>>G.vexnum;
 cout<<endl;
 cout<<"边数:";  
 cin>>G.arcnum; 
 cout<<endl;
 for(i=1;i<=G.vexnum;i++)
 {
  G.vertices[i].data=i;
  G.vertices[i].firstarc=NULL;
 }
 for(k=1;k<=G.arcnum;k++)
 {
  cout<<"请输入第"<<k<<"条边:";
  cout<<"from:";
  cin>>i;
  cout<<"to:";
  cin>>j;
  cout<<"输入权值:";
  cin>>w;
  p=(ArcNode*)malloc(sizeof(ArcNode));
  p->adjvex=j;
  p->weight=w;
  p->nextarc=G.vertices[i].firstarc;
  G.vertices[i].firstarc=p;
 }
}
 FGRAPH(ALGraph &G,int E,int n)
 {
	 
	int i,temp,*value;
    int *path,*D;
    ArcNode *s;
	VNode *vnode;
    value=(int*)malloc(sizeof (int));
    path=(int*)malloc(sizeof (int));
    D=(int*)malloc(sizeof (int));
    for(i=1;i<=n;i++)
    value[i]=0;
   for(i=n-1;i>=1;i--)
   {
	   s=G.vertices[i].firstarc;
      value[i]=s->weight+value[s->adjvex];
      D[i]=s->adjvex;
      s=s->nextarc;
      while(s)
      {
	 temp=s->weight+value[s->adjvex];
	 if(temp<value[i])
	 {
	    value[i]=temp;
	    D[i]=s->adjvex;
	 }
	 s=s->nextarc;
      }
   }
	  path[1]=1;
	  path[G.vexnum]=n;
	  for(i=2;i<=G.vexnum;i++)
		  path[i]=D[path[i-1]];
	  cout<<"Path:";
	  for(i=1;i<G.vexnum;i++)
	  {
		  cout<<path[i]<<"-->";
	  }
   }
 void main()
{ 
	ALGraph G;
	int d;
	CreateDG(G);
	FGRAPH(G,G.arcnum,G.vexnum);
}