#include <iostream.h>
#include <cstring>
#include <stdlib.h>
#include<stdio.h>
#include <conio.h>
#include <ctype.h>
#define MAXVTXNUM 20 //图中顶点数的最大值
#define MAXSIZE 1000
#define MAX 30
#ifndef x
#define x 1
typedef struct
{
char *name; //该顶点的名称
char *info; //景点信息
}VertexType; //顶点类型
#endif
#ifndef xx
#define xx 1
typedef struct
{
int lengh; //边的权值
int ivex,jvex; //边两端的顶点号
}EdgeType; // 变的类型
#endif
#ifndef xxx
#define xxx 1
typedef struct EdgeNode
{
EdgeType elem;
EdgeNode *ilink,*jlink;
}EdgeNode, *EdgePtr; //边的结点类型
#endif
#ifndef xxxx
#define xxxx 1
typedef struct
{
VertexType data;
EdgePtr firstEdge; //指向第一条依附于该顶点的边的指针类型
}VNode; //顶点类型
#endif
#ifndef xxxxx
#define xxxxx 2
typedef struct
{
VNode Adjmulist[MAXVTXNUM]; //邻接多重表
int vexNum, edgeNum; //图中的顶点数和边数
}GraphType; //图的类型
#endif
#ifndef xxxxxx
#define xxxxxx 3
typedef struct
{
int vx, vy;
}Edge;
typedef struct
{
Edge edges[MAXVTXNUM]; //路径中边的序列
int len; //路径中边的数目
}PathType;
#endif
#ifndef xxxxxxx
#define xxxxxxx 4
typedef struct
{
char *Vertices[MAXSIZE]; //路径中景点的序列
int num;
}PType;
#endif
void InitGraph(GraphType &g); //初始化邻接多重表，表示一个空图
//在途中查找其景点名和uname相同的顶点。若存在，则以i返回其在临界多重表中的位置并返回TURE；
bool LocateVex(GraphType &g, char *uname, int &i);
void GetVex(GraphType g, int i, VertexType &v);
EdgePtr FirstEdge(GraphType g, int vi);
void NextEdge(GraphType g, int vi, EdgePtr p, int &vj, EdgePtr &q);
void InsertVex(GraphType &g, VertexType v);
void InsertEdge(GraphType &g, EdgeType e);
void DeleteVex(GraphType &g, VertexType v);
void DeleteEdge(GraphType &g, EdgeType e);
void InitPath(PathType &pa); //初始化pa为一条空路径
void CopyPath(PathType &p1, PathType &p2); //复制路径p1=p2
void InsertPath(PathType &pa, int v, int w); //在路径pa中插入一条边（v,w）
int PathLength(PathType pa); //返回路径pa的长度
void OutPath(GraphType g, PathType pa, PType &vtxes); //将路径转化为景点的名序列
void Initialization();
void ReadCommand(char &cmd);
void Interpret(char cmd);
void CreatGraph(GraphType &g, FILE *f);
void GetShortestPath(GraphType g, char *sname, char *tname,
int &pathLength, PType &PathInfo);
void ShortestPath(GraphType g, int st, int nd,
int &pathLength, PType &PathInfo)；
//#include<string>
/////////////////////////////////////////////////////////////
////////////////////// 图设计部分 ///////////////////////
/////////////////////////////////////////////////////////////
void InitGraph(GraphType &g)
{
g.vexNum = g.edgeNum = 0;
}//InitGraph
bool LocateVex(GraphType &g, char *uname, int &i)
{
for(i=0; i<g.vexNum; i++)
if(!strcmp(uname, g.Adjmulist[i].data.name))
{
return true;
break;
}
return false;
}//LocateVex
EdgePtr FirstEdge(GraphType g, int vi)
{//返回图g中指向依附于顶点vi的第一条边的指针g.Adjmulist[i].data
return
g.Adjmulist[vi].firstEdge;
}//FirstEdge
void GetVex(GraphType g, int i, VertexType &v)
{
if(i<0)
cout<<"这两点间无路径可通！"<<endl;
else
v = g.Adjmulist[i].data;
}//GetVex
void NextEdge(GraphType g, int vi, EdgePtr p, int &vj, EdgePtr &q)
{
if(p->elem.ivex==vi )
{
q = p->ilink;
vj = p->elem.jvex;
}
else
{
q = p->jlink;
vj = p->elem.ivex;
}
}//NextEdge
void InsertEdge(GraphType &g, EdgeType e)
{
EdgePtr p;
p = (EdgePtr)malloc(sizeof(EdgeNode));
p->elem =e;
p->ilink = FirstEdge(g,e.ivex);
p->jlink = FirstEdge(g, e.jvex);
g.Adjmulist[e.ivex].firstEdge = g.Adjmulist[e.jvex].firstEdge = p;
}//InsertEdge
void InsertVex(GraphType &g, VertexType v, int i)
{
//在图g的邻接多重表中添加一个顶点v
g.Adjmulist[i].data.name = new char[MAXSIZE];
g.Adjmulist[i].data.info = new char[MAXSIZE];
strcpy(g.Adjmulist[i].data.name,v.name);
strcpy(g.Adjmulist[i].data.info,v.info);
g.Adjmulist[i].firstEdge = NULL;
}
///////////////////////////////////////////////////////////////////////
///////////////////////// 路径类型 ////////////////////////////////
///////////////////////////////////////////////////////////////////////
void InitPath(PathType &pa)
{
pa.len = 0;
}//InitPath
int PathLengh(PathType pa)
{
return pa.len;
}//PathLengh
void CopyPath(PathType &p1, PathType &p2)
{
//复制路径p1=p2
for(int i =0; i<p2.len; i++)
{
p1.edges[i].vx = p2.edges[i].vx;
p1.edges[i].vy = p2.edges[i].vy;
}
p1.len = p2.len;
}//CopyPath
void InsertPath(PathType &pa, int v, int w)
{
//在路pa径中插入一条边（v，w）
pa.edges[pa.len].vx = v;
pa.edges[pa.len].vy = w;
pa.len++;
}//InsertPath
void OutPath(GraphType g, PathType pa, PType &vtxes)
{
//将路径转化为景点的名序列
int m = 0;
VertexType vtx;
vtx.info = new char[MAXSIZE];
vtx.name = new char[MAXSIZE];
for(int i=0; i<pa.len; i++)
{
vtxes.Vertices[m] = new char[MAXSIZE];
GetVex(g, pa.edges[i].vx, vtx);
strcat(vtx.name,vtx.info);
strcpy(vtxes.Vertices[m++], vtx.name);
}
GetVex(g, pa.edges[pa.len-1].vy, vtx);
vtxes.Vertices[m] = new char[MAX];
strcpy(vtxes.Vertices[m] , vtx.name);
strcat(vtxes.Vertices[m] , vtx.info);
vtxes.num = m;
}//OutPath
/////////////////////////////////////////////////////////
//////////////// 主程序部分//////////////////////////////
/////////////////////////////////////////////////////////
void Initialization(GraphType &ga)
{
system("cls");
FILE *fin = fopen("test.txt", "r");
CreatGraph(ga, fin);
}//Initialization
void PrintScenery(char *sname, GraphType g)
{
for(int j=0; j<g.vexNum;j++)
if(!strcmp(sname,g.Adjmulist[j].data.name))
{
cout<<"输出的景点名为："<<sname<<endl;
cout<<"景点信息为: "<<g.Adjmulist[j].data.info<<endl;
break;
}
}//PrintScenery
void ReadCommand(char &cmd)
{
do{
cout<<"读入操作符命令：(s/S/V/v/Q/q ?)" ;
cin>>cmd;
}
while (cmd!='s'&& cmd!='S'&& cmd!='v'&& cmd!='V'&& cmd!='q'&& cmd!='Q');
}//ReadCommand
void PrintPath(PType spath, int pathlen)
{
cout<<"输出所经历路径信息为："<<endl;
for(int i=0; i<spath.num; i++)
cout<<"----"<<spath.Vertices[i]<<"----";
cout<<endl;
cout<<"所经历的最短路径长度为："<<pathlen<<endl;
}//PrintPath
void Interpret(char cmd, GraphType g)
{
char *sname=new char[MAXSIZE];
char *tname=new char[MAXSIZE];
int pathlen;
PType spath;
switch(cmd)
{
case 's':
cout<<"读入景点名称： ";
cin>>sname;
PrintScenery(sname, g);
break;
case 'S':
cout<<"读入景点名称： ";
cin>>sname;
PrintScenery(sname,g);
break;
case 'v':
cout<<"读入起点名称： " ;
cin>>sname;
cout<<"读入终点名称： ";
cin>>tname;
GetShortestPath(g, sname,tname,pathlen,spath);
PrintPath(spath, pathlen);
break;
case 'V':
cout<<"读入起点名称： " ;
cin>>sname;
cout<<"读入终点名称： ";
cin>>tname;
GetShortestPath(g, sname,tname,pathlen,spath);
PrintPath(spath, pathlen);
break;
case 'q':
break;
case 'Q':
break;
}
}//Interpret
void CreatGraph(GraphType &g, FILE *f)
{
VertexType v;
InitGraph(g);
EdgeType e;
v.info = new char[MAXSIZE];
v.name = new char[MAXSIZE];
fscanf(f,"%d",&g.edgeNum);
fgetc(f);
fscanf(f,"%d",&g.vexNum);
for(int i=0; i<g.vexNum; i++)
{
fscanf(f, "%s",v.name);
fgetc(f);
fscanf(f, "%s",v.info);
InsertVex(g,v,i);
}
for(int k=0; k<g.edgeNum; k++)
{
fscanf(f,"%d",&e.ivex);
fgetc(f);
fscanf(f,"%d",&e.jvex);
fgetc(f);
fscanf(f,"%d",&e.lengh);
if(e.lengh)
InsertEdge(g,e);
}
}//CreatGraph
void GetShortestPath(GraphType g, char *sname, char *tname,
int &pathLengh,PType &PathInfo)
{
int sv,tv;
LocateVex(g,sname,sv);
LocateVex(g, tname, tv);
ShortestPath(g,sv,tv,pathLengh,PathInfo);
}//GetShortestPath
void InitSet(bool *ss, GraphType g)
{
for(int i=0; i<g.vexNum; i++)
ss[i] = false;
}
void PutInSet(int st, bool ss[MAXVTXNUM])
{
ss[st] = true;
}//PutInSet
int minval(int *dist, GraphType g, bool *ss)
{
int min = -1;
for(int i =0; i<g.vexNum; i++)
if(!ss[i])
{
if(min == -1)
min = i;
else if(dist[min]>dist[i])
min = i;
}
return min;
}//minval
bool InSet(int w, bool *ss)
{
if(ss[w])
return true;
else
return false;
}
void ShortestPath(GraphType g, int st, int nd, int &pathLengh,
PType &PathInfo)
{
unsigned int maxint = 10000000;
int dist[MAXVTXNUM];
PathType path[MAXVTXNUM];
int adjvex;
bool ss[MAXVTXNUM];
int min,v,w;
int count=0;
EdgePtr p,q;
for(int i=0; i<g.vexNum; i++)
{
dist[i] = maxint;
InitPath(path[i]);
}
p = FirstEdge(g, st);
while(p)
{
NextEdge(g,st,p,adjvex,q);
dist[adjvex] = p->elem.lengh;
InsertPath(path[adjvex],st,adjvex);
p = q;
}
bool found = false;
InitSet(ss,g);
PutInSet(st,ss);
w = st;
while(!found)
{
min = minval(dist,g,ss);
if(min==nd)
{
InsertPath(path[nd],nd,w);
found = true;
}
else
{
v = min;
PutInSet(v,ss);
p = FirstEdge(g,v);
while(p)
{
NextEdge(g,v,p,w,q);
if(!InSet(w,ss) && dist[v]+p->elem.lengh<dist[w])
{
dist[w] = dist[v]+p->elem.lengh;
CopyPath(path[w], path[v]);
InsertPath(path[w], v, w);
}
p = q;
}//while(p)
}//else
}//while(!found)
pathLengh = dist[nd];
OutPath(g, path[nd], PathInfo);
}//ShortestPath
//////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////
void main()
{
GraphType ga;
char cmd;
Initialization(ga);
cout<<"****************************************************************"<<endl;
cout<<"******* 班级：030524班 学号：03051433 ********"<<endl;
cout<<"******* 制作人：王甲楼 西安电子科技大学 ********"<<endl;
cout<<"***************** 符命令注解：S/s表示显示 *****************"<<endl;
cout<<"***************** V/v表示开始查询最短路径 ****************"<<endl;
cout<<"***************** Q/q 表示退出 ****************"<<endl;
cout<<"****************************************************************"<<endl;
cout<<endl<<endl<<endl;
do
{
ReadCommand(cmd);
Interpret(cmd, ga);
}
while(cmd!= 'q' && cmd!='Q');
}//main
////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////
