六.cpp

求单源最短路径(要求用Dijkstra算法求得）

#include<iostream.h>
#define INFINITY 10000
#define MAX_VERTEX_NUM 20
typedef struct ArcCell
{
	int adj; //权值 
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
	char vexs[MAX_VERTEX_NUM];
	AdjMatrix arcs;
	int vexnum,arcnum;
}MGraph;
int LocateVex(MGraph G,char v)
{
	for(int i=0;i<G.vexnum;i++)
	{
		if(G.vexs[i]==v)
			return i;
	}
	return 0;
}
int FirstAdjVex(MGraph G,char v)
{
	int i,j;
	i=LocateVex(G,v);
	for(j=0;j<G.vexnum;j++)
	{
		if(G.arcs[i][j].adj!=INFINITY)
			return j;
	}
	return 0;
}
int NextAdjVex(MGraph G,char v,char w)
{
	int i,j;
	i=LocateVex(G,v);
	j=LocateVex(G,w);
	while(j<G.vexnum)
	{
		j++;
		if(G.arcs[i][j].adj!=INFINITY)
			return j;
	}
	return 0;
}
void CreateDG(MGraph &G)
{
	int i,j,k;
	int w;
	char v1,v2;
	cout<<"输入图的结点数：";
	cin>>G.vexnum;
	cout<<"输入图的边数：";
	cin>>G.arcnum;
	cout<<"输入图的结点："<<endl;
	for(i=0;i<G.vexnum;i++)
		cin>>G.vexs[i];
	for(i=0;i<G.vexnum;i++)
	{
		for(j=0;j<G.vexnum;j++)
		{
			G.arcs[i][j].adj=INFINITY;
		}
	}
	for(k=0;k<G.arcnum;k++)
	{
		cout<<"输入第"<<k+1<<"条边所对应的两个结点，及该边的权值：";
		cin>>v1>>v2>>w;
		i=LocateVex(G,v1);
		j=LocateVex(G,v2);
		G.arcs[i][j].adj=w;
	}
}
typedef struct X
{
	int final[MAX_VERTEX_NUM];
	int D[MAX_VERTEX_NUM];
	int pre[MAX_VERTEX_NUM];
}DIJ;
void ShortestPath_DIJ(MGraph G,char v,DIJ &A)
{
	int i,j,k;
	int min;
	int temp;
	k=LocateVex(G,v);
	for(i=0;i<G.vexnum;i++)
	{
		A.D[i]=G.arcs[k][i].adj;
		A.final[i]=0;A.pre[i]=-1;
		if(G.arcs[k][i].adj!=INFINITY)
			A.pre[i]=k;
	}
	A.D[k]=0;
	A.final[k]=1;
	A.pre[k]=-1;
	for(i=1;i<G.vexnum;i++)
	{
        min=INFINITY;
		for(j=0;j<G.vexnum;j++)
		{
			if(!A.final[j]&&A.D[j]<min)
			{
				min=A.D[j];
				temp=j;
			}
		}
		A.final[temp]=1;
		for(k=0;k<G.vexnum;k++)
		{
			if(!A.final[k]&&(min+G.arcs[temp][k].adj<A.D[k]) )
			{
				A.D[k]=min+G.arcs[temp][k].adj;
				A.pre[k]=temp;
			}
		}
	}
}
void Printf(DIJ A,char c,MGraph G)
{
	int k;
	for(int i=0;i<G.vexnum;i++)
	{
		k=i;
		cout<<"从"<<G.vexs[i]<<"到"<<c<<"的最短路径为：";
		while(k!=-1)
		{
		    cout<<G.vexs[k]<<"  ";
			k=A.pre[k];
		}
		cout<<endl;
		cout<<"路径长度为："<<A.D[i]<<endl;
	}
}
void main()
{
		MGraph G;
		CreateDG(G);
		DIJ A;
		ShortestPath_DIJ(G,'5',A);
		Printf(A,'5',G);
}