shortestpath.cpp

最短路径问题 非常重要 最短路径问题 非常实用 最短路径问题 非常好

#include<iostream>
#include<iomanip>
using namespace std;
#define INFINITY 32767
#define MAX_VERTEX_NUM 20
#define MAX_NAME 10
#define MAX_INFO 20
#define TRUE 1
#define FALSE 0
typedef int VRType;
typedef int Status;
typedef char InfoType;
typedef VRType ShortPathTable[MAX_VERTEX_NUM];
typedef Status PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

/*struct InfoType
{
	VRType weight;
};

struct ArcNode
{
	int adjvex;
	InfoType *info;
	ArcNode *nextarc;
};*/

typedef struct
{
	VRType adj;
	InfoType *Info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

struct VerTexType
{
	char name[MAX_NAME];
};

struct MGraph
{
	VerTexType vexs[MAX_VERTEX_NUM];
	AdjMatrix arcs;
	int vexnum,arcnum;
};

int LocateVex(MGraph G,VerTexType u)
{
	int i;
	for(i=0;i<G.vexnum;i++)
		if(strcmp(u.name,G.vexs[i].name)==0)
			return i;
return -1;
}

VerTexType GetVex(MGraph G,int v)
{
	if(v>=G.vexnum||v<0)
		exit(-2);
	return G.vexs[v];
}

void InputArc(InfoType *&arc)
{
	char s[MAX_INFO];
	int m;
	cout<<"请输入该弧（边）的相关信息（ <"<<MAX_INFO<<" 个字符）";
	cin>>s;
	m=strlen(s);
	if(m)
	{
		arc=(char *)malloc((m+1)*sizeof(char));
		strcpy(arc,s);
	}
}

void Input(VerTexType &ver)
{
	cin>>ver.name;
}

void Visit(VerTexType ver)
{
	cout<<setw(5)<<ver.name;
}

void CreateDN(MGraph &G)
{
	int i,j,k,IncInfo;
	VRType w;
	VerTexType v1,v2;
	cout<<"请输入有向网 G 的顶点数，弧数，弧是否含相关信息（1：是 0：否）";
	cin>>G.vexnum>>G.arcnum>>IncInfo;
	cout<<"请输入"<<G.vexnum<<"个顶点的值（名称< "<< MAX_NAME<<"个字符）："<<endl;
	for(i=0;i<G.vexnum;++i)
		Input(G.vexs[i]);
	for(i=0;i<G.vexnum;++i)
		for(j=0;j<G.vexnum;++j)
		{
			G.arcs[i][j].adj=INFINITY ;
			G.arcs[i][j].Info=NULL;
		}
	cout<<"请输入"<<G.arcnum<<" 条弧的弧尾 弧头 权值："<<endl;;
	for(k=0;k<G.arcnum;++k)
	{
		cin>>v1.name>>v2.name>>w;
		i=LocateVex(G,v1);
		j=LocateVex(G,v2);
		G.arcs[i][j].adj=w;
		if(IncInfo)
			InputArc(G.arcs[i][j].Info);
	}
}

void ShortPath(MGraph G,int v0,PathMatrix p,ShortPathTable d)
{
	int v,w,i,j;
	VRType min;
	int final[MAX_VERTEX_NUM];
	for(v=0;v<G.vexnum;v++)
	{
		final[v]=FALSE;
		d[v]=G.arcs[v0][v].adj;
		for(w=0;w<G.vexnum;++w)
			p[v][w]=FALSE;
		if(d[v]<INFINITY)
			p[v][v0]=p[v][v]=TRUE;
	}
	d[v0]=0;
	final[v0]=TRUE;
	for(i=1;i<G.vexnum;i++)
	{
		min=INFINITY;
		for(w=0;w<G.vexnum;w++)
			if(!final[w] && d[w]<min)
			{
				v=w;
				min=d[w];
			}
		final[v]=TRUE;
		for(w=0;w<G.vexnum;++w)
			if(!final[w] && min<INFINITY && G.arcs[v][w].adj<INFINITY &&(min+G.arcs[v][w].adj<d[w]))
			{
				d[w]=min+G.arcs[v][w].adj;
				for(j=0;j<G.vexnum;++j)
					p[w][j]=p[v][j];
				p[w][w]=TRUE;
			}
	}
}

void Display(MGraph G)
{
	int i,j;
	char s1[7]="边",s2[3]="-";
	cout<<G.vexnum<<"个顶点，依次是：";
	for(i=0;i<G.vexnum;i++)
		Visit(GetVex(G,i));
	cout<<endl;
	cout<<"G.arcs.adj:"<<endl;
	for(i=0;i<G.vexnum;i++)
	{
		for(j=0;j<G.vexnum;j++)
			cout<<setw(8)<<G.arcs[i][j].adj;
		cout<<endl;
	}
	cout<<"G.arcs.info:"<<endl;
	cout<<"弧尾  弧头  该"<<s1 <<"的信息："<<endl;
	for(i=0;i<G.vexnum;i++)
		for(j=0;j<G.vexnum;j++)
			if(G.arcs[i][j].Info)
			{
				cout<<G.vexs[i].name<<""<<G.vexs[j].name<<"";
				cout<<G.arcs[i][j].Info<<endl;
			}
}

void main()
{
	int i,j;
	MGraph g;
	PathMatrix p;
	ShortPathTable d;
	CreateDN(g);
	Display(g);
	ShortPath(g,0,p,d);
	cout<<"最短路径数组P[i][j]如下："<<endl;
	for(i=0;i<g.vexnum;++i)
	{
		for(j=0;j<g.vexnum;++j)
			cout<<setw(6)<<p[i][j];
		cout<<endl;
	}
	cout<<g.vexs[0].name<<"到各顶点的最短路径长度为："<<endl;
	for(i=0;i<g.vexnum;i++)
		if(i!=0)
			cout<<g.vexs[0].name<<"->"<<g.vexs[i].name<<" :"<<d[i]<<endl;
}