path.cpp

来自「常用算法与数据结构原代码」· C++ 代码 · 共 124 行

#define N 30
#include <iostream.h>
typedef struct node{
	int vno,weight;
	node *next;
} edgeNode;

typedef edgeNode *graph[N];

typedef struct {
	int bv,tv,t,pt;
} AST;

typedef AST Ast[N];
int creat(graph g)
{
	int vn,en,k,i,j,w;
	edgeNode *p;
	cout<<"输入顶点数:";
	cin>>vn;
	cout<<"输入边数:";
	cin>>en;
	for (k=0;k<vn;k++)
		g[k]=NULL;
	for (k=0;k<en;k++)
	{
		cout<<"输入边 :";
		cin>>i >>j >>w;
		p=new edgeNode;
		p->vno=j;
		p->weight=w;
		p->next=g[i];
		g[i]=p;
	}
	return vn;
}

int mainpath(graph g,int n)
{
	int top,count,i,j,k;
	int inCount[N],queue[N],est[N],elt[N],alt[N];
	edgeNode *p;
	Ast ast;
	for (i=0;i<n;i++)
	{
		inCount[i]=0;
		est[i]=0;
		elt[i]=32767;
	}
	for (i=0;i<n;i++)
		for (p=g[i];p!=NULL;p=p->next)
		{
			j=p->vno;
			inCount[j]++;
		}
	top=-1;
	for (i=0;i<n;i++)
		if (inCount[i]==0)
		{
			inCount[i]=top;
			top=i;
			break;
		}
	count=0;
	while (top>=0)
	{
		queue[count++]=top;
		p=g[top];
		j=top;
		top=inCount[top];
		for (;p!=NULL;p=p->next)
		{
			k=p->vno;
			if (est[k]<est[j]+p->weight)
				est[k]=est[j]+p->weight;
			if (--inCount[k]==0)
			{
				inCount[k]=top;
				top=k;
			}
		}
	}
	if (count!=n)
		return -1;
	elt[queue[n-1]]=est[queue[n-1]];
	for (i=n-2;i>=0;i--)
	{
		k=queue[i];
		p=g[k];
		for (;p!=NULL;p=p->next)
			if (elt[k]>elt[p->vno]-p->weight)
				elt[k]=elt[p->vno]-p->weight;
	}
	count=0;
	for (i=0;i<n-1;i++)
	{
		j=queue[i];
		p=g[j];
		for (;p!=NULL;p=p->next)
		{
			ast[count].bv=j;
			ast[count].tv=p->vno;
			ast[count].t=est[j];
			ast[count].pt=p->weight;
			count++;
		}
	}
	for (i=0;i<count;i++)
		alt[i]=elt[ast[i].tv]-ast[i].pt;
	for (i=0;i<count;i++)
		if (alt[i]==ast[i].t)
			cout<<ast[i].bv<<"->"<<ast[i].tv<<"  "<<ast[i].pt<<endl;
	return 0;
}


void main()
{
	graph g;
	int n;
	n=creat(g);
	mainpath(g,n);
}