tu.cpp

有向加权图的建立、显示和寻找最短路径

//有向加权图的建立、显示和寻找最短路径
#include"stdlib.h"
#include<iostream.h>
#define MAXVEX 100
#define MAX 32000
struct vertex      //定义图
{
int num;   //顶点编号
char data;//顶点信息
};
typedef struct graph
{
struct vertex vexs[MAXVEX];  //顶点编号
int vexnum;       //顶点数
int arcnum;       //边数
int edges[MAXVEX][MAXVEX];    //边的集合
}adjmax;

adjmax creatgraph()   //图的建立、输入和存储
{
int i,j,k,w;
int n,e;
char b,t;
adjmax adj;
cout<<"点数(n)和边数(e):";
cin>>n>>e;
adj.vexnum=n;     //输入顶点数
adj.arcnum=e;     //输入边数
for(i=1;i<=n;i++)
	{
    cout<<"第"<<i<<"顶点信息:";
	cin>>adj.vexs[i].data;    //输入顶点信息
	adj.vexs[i].num=i;        //定义顶点编号
	}
for(i=1;i<=n;i++)
 for(j=1;j<=n;j++)
  adj.edges[i][j]=MAX;        //初始化边的权值
for(k=1;k<=e;k++)
	{
	cout<<"第"<<k<<"条边:"<<"\n";
	cout<<"   起点:";         //输入边的起点
	cin>>b;
	cout<<"   终点:";         //输入边的终点
	cin>>t;
	cout<<"   权值:";         //输入边的权值
	cin>>w;
	i=1;                      //判断输入的顶点是否在顶点集合内
	while(i<=n&&adj.vexs[i].data!=b)
        i++;
	if(i>n)
		{
        	cout<<"你的输入的起点不存在!";
			exit(0);
		}
	j=1;
	while(j<=n&&adj.vexs[j].data!=t)
        j++;
	if(j>n)
		{
        	cout<<"你的输入的终点不存在!";
			exit(1);
        }
	adj.edges[i][j]=w;          //再定义边的权值
	}
return(adj);
}
void Traverse(adjmax adj)        //显示图
{
int i,j;
for(i=1;i<=adj.vexnum;i++)
	{
	cout<<"顶点"<<adj.vexs[i].data<<"出发的边：";
	for(j=1;j<=adj.vexnum;j++)
	if(adj.edges[i][j]<MAX)
	cout<<"\t"<<adj.vexs[i].data<<"->"<<adj.vexs[j].data<<"它的权值："<<adj.edges[i][j];    //输出边的起点和终点
	cout<<"\n";
	}
}
void shortpath(adjmax adj)  //寻找最短路径
{
int dist[MAXVEX],path[MAXVEX],s[MAXVEX];
int w,u,vnum,wm,k,v0,i;
char c;
cout<<"输入源点:";    //输入源点
cin>>c;
for(i=1;i<=adj.vexnum;i++)  //寻找顶点编号
 if(adj.vexs[i].data==c)
   v0=adj.vexs[i].num;
for(w=1;w<=adj.vexnum;w++)
	{
	dist[w]=adj.edges[v0][w];
	if(adj.edges[v0][w]<MAX)
	path[w]=v0;
	}
for(w=1;w<=adj.vexnum;w++)   //初始化从源点出发的最短路径的终点的集合当s[w]=1属于集合内
s[w]=0;
s[v0]=1;            //定义源点
vnum=1;
u=v0;
while(vnum<adj.vexnum)    //寻找源点到各点的最短路径
	{
 	wm=MAX;
	for(w=1;w<=adj.vexnum;w++)
	 if(s[w]==0&&dist[w]<wm)
		{
		u=w;
		wm=dist[w];
		}
		s[u]=1;     //添加顶点到最短路径的终点的集合内
	  for(w=1;w<=adj.vexnum;w++)   //修改源点到最短路径的终点的集合外可达最短路径长度
	  if(s[w]==0&&dist[u]+adj.edges[u][w]<dist[w])
		{
		dist[w]=dist[u]+adj.edges[u][w];
		path[w]=u;
		}
	vnum++;
	}
for(w=1;w<=adj.vexnum;w++)     //打印最短路径
  if(s[w]==1)
	{
	k=w;               //打印有路径的顶点
	while(k!=v0)
		{
		cout<<adj.vexs[k].data<<"<-";
		k=path[k];
		}
	cout<<adj.vexs[k].data;
	if(dist[w]==MAX)
	   cout<<"\t"<<"源点"<<"\n";
	else
	   cout<<"\t"<<dist[w]<<"\n";
	}
  else         //打印没有路径的顶点
	{
	cout<<adj.vexs[w].data<<"<-"<<adj.vexs[v0].data;
	cout<<"\t没有路径!\n";
	}
}
void main()  //主程序
{
char c;
adjmax adj;   
adj=creatgraph();
Traverse(adj);
while(c!='n')   //设置循环
	{
	shortpath(adj);
	cout<<"继续查找请键入（y）否则键入（n）结束:";
	cin>>c;
	}
}