one_shortroad.cpp

本次试验是讨论单源点的最短路径问题:给带权有向图和源点V到G中其余各顶点的最短路径。

#include<iostream.h>
#define MAX_VERTEX 100
#define INFINITY 10000//在这里相当于无穷大，在邻接表用以初始化，表示两条边不相连。
typedef char VertexType;
typedef int VRType;
typedef bool** PathMatrix;
typedef VRType* ShortPathTable;
typedef struct ArcCell
{
	VRType adj;
}ArcCell,AdjMatrix[MAX_VERTEX][MAX_VERTEX];
typedef struct
{
	VertexType ves[MAX_VERTEX];
    AdjMatrix arcs;
	int vexnum,arcnum;//当前的顶点数和弧数
}MGraph;

int LocateVex(MGraph M,char c)
{
	int i=0, k=-1;
	while(i<M.vexnum)
	{
		if(M.ves[i]==c)
			return i;
		i++;
	}
	return k;
}
//用邻接表创建有向图
void CreatDG(MGraph&M)                                                                                                                                                          
{
	int i,j,k;
	char v1,v2;
	VRType w;
	cout<<"请输入有向图的结点数和弧数:";
	cin>>M.vexnum>>M.arcnum;
	cout<<"请输入结点:";
	for(i=0;i<M.vexnum;i++)
	{
		cin>>M.ves[i];
	}
	for(i=0;i<M.vexnum;i++)
	{
		for(j=0;j<M.vexnum;j++)
		{
			M.arcs[i][j].adj=88;
		}
	}
	for(i=0;i<M.vexnum;i++)
	{
		for(j=i;j<M.vexnum;j++)
		{
			M.arcs[i][j].adj=INFINITY;
		    M.arcs[j][i].adj=INFINITY;
		}
	}
	cout<<"请输入弧权值（格式：A B 50。其中A B为顶点）:"<<endl;
	for(k=0;k<M.arcnum;k++)
	{
		cin>>v1>>v2>>w;
		i=LocateVex(M,v1);
		j=LocateVex(M,v2);
		M.arcs[i][j].adj=w;
	}
	cout<<"图创建完毕"<<endl;
}

//用迪杰斯特拉算法找出最短路径
void ShortestPath_DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D)
{
	int v,w,i,k,m=1;
	VRType min;
	int *a=new int[G.vexnum];
	a[0]=v0;
	bool *final;
	final=new bool[G.vexnum];
	for(v=0;v<G.vexnum;++v)
	{
		final[v]=false;
		D[v]=G.arcs[v0][v].adj;
		for(w=0;w<G.vexnum;++w)
		{
			if(D[v]<INFINITY)
			{
				P[v][v0]=true;
				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])
			{
				if(D[w]<min)
				{
					v=w;
					min=D[w];
				}
			}
		}
		final[v]=true;
		if(a[m-1]!=v)
		{
			a[m]=v;
		    m++;
			for(k=0;k<m;k++)
			{
				cout<<G.ves[a[k]]<<" ";
			}
			cout<<"迪杰斯特拉算法得出路径长度："<<D[v]<<endl;
		}
		for(w=0;w<G.vexnum;++w)
		{
			if(!final[w]&&min+G.arcs[v][w].adj<D[w])
			{
				D[w]=min+G.arcs[v][w].adj;
				P[w]=P[v];
				P[w][w]=true;
			}
		}
	}
}

void main()
{
	MGraph M;
	cout<<"开始构造初始图"<<endl;
	CreatDG(M);
	PathMatrix P=new bool*[M.vexnum];   
    for(int i=0;i<M.vexnum;i++)
		P[i]=new bool[M.vexnum];
	VertexType u;
	cout<<"请输入源点：";
	cin>>u;
	ShortPathTable D=new VRType[M.vexnum];
	int v=LocateVex(M,u);
	if(v<0)
	{
		cout<<"该结点不存在图中"<<endl;
	}
	else
	{
		ShortestPath_DIJ(M,v,P,D);
	}
}