//有向加權(quán)圖的建立、顯示和尋找最短路徑
#include"stdlib.h"
#include<iostream.h>
#define MAXVEX 100
#define MAX 32000
struct vertex      //定義圖
{
int num;   //頂點(diǎn)編號
char data;//頂點(diǎn)信息
};
typedef struct graph
{
struct vertex vexs[MAXVEX];  //頂點(diǎn)編號
int vexnum;       //頂點(diǎn)數(shù)
int arcnum;       //邊數(shù)
int edges[MAXVEX][MAXVEX];    //邊的集合
}adjmax;

adjmax creatgraph()   //圖的建立、輸入和存儲(chǔ)
{
int i,j,k,w;
int n,e;
char b,t;
adjmax adj;
cout<<"點(diǎn)數(shù)(n)和邊數(shù)(e):";
cin>>n>>e;
adj.vexnum=n;     //輸入頂點(diǎn)數(shù)
adj.arcnum=e;     //輸入邊數(shù)
for(i=1;i<=n;i++)
	{
    cout<<"第"<<i<<"頂點(diǎn)信息:";
	cin>>adj.vexs[i].data;    //輸入頂點(diǎn)信息
	adj.vexs[i].num=i;        //定義頂點(diǎn)編號
	}
for(i=1;i<=n;i++)
 for(j=1;j<=n;j++)
  adj.edges[i][j]=MAX;        //初始化邊的權(quán)值
for(k=1;k<=e;k++)
	{
	cout<<"第"<<k<<"條邊:"<<"\n";
	cout<<"   起點(diǎn):";         //輸入邊的起點(diǎn)
	cin>>b;
	cout<<"   終點(diǎn):";         //輸入邊的終點(diǎn)
	cin>>t;
	cout<<"   權(quán)值:";         //輸入邊的權(quán)值
	cin>>w;
	i=1;                      //判斷輸入的頂點(diǎn)是否在頂點(diǎn)集合內(nèi)
	while(i<=n&&adj.vexs[i].data!=b)
        i++;
	if(i>n)
		{
        	cout<<"你的輸入的起點(diǎn)不存在!";
			exit(0);
		}
	j=1;
	while(j<=n&&adj.vexs[j].data!=t)
        j++;
	if(j>n)
		{
        	cout<<"你的輸入的終點(diǎn)不存在!";
			exit(1);
        }
	adj.edges[i][j]=w;          //再定義邊的權(quán)值
	}
return(adj);
}
void Traverse(adjmax adj)        //顯示圖
{
int i,j;
for(i=1;i<=adj.vexnum;i++)
	{
	cout<<"頂點(diǎn)"<<adj.vexs[i].data<<"出發(fā)的邊：";
	for(j=1;j<=adj.vexnum;j++)
	if(adj.edges[i][j]<MAX)
	cout<<"\t"<<adj.vexs[i].data<<"->"<<adj.vexs[j].data<<"它的權(quán)值："<<adj.edges[i][j];    //輸出邊的起點(diǎn)和終點(diǎn)
	cout<<"\n";
	}
}
void shortpath(adjmax adj)  //尋找最短路徑
{
int dist[MAXVEX],path[MAXVEX],s[MAXVEX];
int w,u,vnum,wm,k,v0,i;
char c;
cout<<"輸入源點(diǎn):";    //輸入源點(diǎn)
cin>>c;
for(i=1;i<=adj.vexnum;i++)  //尋找頂點(diǎn)編號
 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++)   //初始化從源點(diǎn)出發(fā)的最短路徑的終點(diǎn)的集合當(dāng)s[w]=1屬于集合內(nèi)
s[w]=0;
s[v0]=1;            //定義源點(diǎn)
vnum=1;
u=v0;
while(vnum<adj.vexnum)    //尋找源點(diǎn)到各點(diǎn)的最短路徑
	{
 	wm=MAX;
	for(w=1;w<=adj.vexnum;w++)
	 if(s[w]==0&&dist[w]<wm)
		{
		u=w;
		wm=dist[w];
		}
		s[u]=1;     //添加頂點(diǎn)到最短路徑的終點(diǎn)的集合內(nèi)
	  for(w=1;w<=adj.vexnum;w++)   //修改源點(diǎn)到最短路徑的終點(diǎn)的集合外可達(dá)最短路徑長度
	  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;               //打印有路徑的頂點(diǎn)
	while(k!=v0)
		{
		cout<<adj.vexs[k].data<<"<-";
		k=path[k];
		}
	cout<<adj.vexs[k].data;
	if(dist[w]==MAX)
	   cout<<"\t"<<"源點(diǎn)"<<"\n";
	else
	   cout<<"\t"<<dist[w]<<"\n";
	}
  else         //打印沒有路徑的頂點(diǎn)
	{
	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')   //設(shè)置循環(huán)
	{
	shortpath(adj);
	cout<<"繼續(xù)查找請鍵入（y）否則鍵入（n）結(jié)束:";
	cin>>c;
	}
}