duoduantu.cpp

经典算法代码--多段图问题。附有详细的注释

#include <iostream.h>


#define Maxint 9999999


typedef struct NODE
{
	int v_num;       //邻接顶点的编号
	int len;         //邻接点与该顶点的费用
	struct NODE *next;     //下一个邻接点
}*Node;

struct Graph
{
	Node node;
	int vexnum,arcnum;         //图当前的顶点数和弧数
};


void CreatGraph(Graph &G)
{
	int i;
	int v1,v2,w;
	Node p,q;

	G.node=new NODE[G.vexnum+1];

    for(i=1;i<=G.vexnum;++i)
	{                            //初始化各个顶点（头节点）
		G.node[i].v_num=i;
		G.node[i].len=0;	
        G.node[i].next=NULL; 
	}

	cout<<"请输入相关连的边及其权值:\n";

    for(i=1; i<=G.arcnum;++i)
	{                               //输入所有边（关联的点）编号
	    cin>>v1>>v2>>w;                //暂存两个相关联的点的编号
        p=new NODE;
	    q=new NODE;

		p->v_num=v2; 
		p->len=w;
        p->next=G.node[v1].next;
        G.node[v1].next=p;


        q->v_num=v1; 
		q->len=w;
        q->next=G.node[v2].next;
        G.node[v2].next=q;
	}
	
}


int fgraph(Graph &G,int *route)
{
	Node pnode;
	int *path=new int[G.vexnum+1];

	int min_cost,*cost = new int[G.vexnum+1];
	for (int i=1;i<=G.vexnum;i++)
	{
		cost[i]=Maxint;
		path[i]=-1;
		route[i]=0;
	}

	cost[G.vexnum]=0;

	for( i=G.vexnum-1;i>=1;i--)
	{
		pnode = G.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=1;

	while ((route[i]!=G.vexnum-1)&&(path[i]!=-1))
	{
		i++;
		route[i] = path[route[i-1]];
	}

	min_cost = cost[1]; 

	cout<<"min_cost为:"<<min_cost<<endl;

	cout<<"路径为:";

	for(i=1;i<=G.vexnum;i++)
		cout<<route[i]<<" ";

	delete []path;
	delete []cost;
	return min_cost;
}


int main()
{
	Graph G;
	int *route;

	cout<<"输入结点个数:";
	cin>>G.vexnum;
	cout<<"请输入边数:";
	cin>>G.arcnum;

	route=new int[G.vexnum];

	CreatGraph(G);
	fgraph(G,route);

	return 0;
}