x.cpp

校园导游图算法--数据结构中有关图的算法 按v求最短路径 按s求信息； 按q退出； 地图在map图像文件里

#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include"graphic.h"
#include"path.h"
#include<iostream.h>
typedef int bool;
//typedef char* string;
/*void Initialization()
{
}
void ReadCommand(char &cmd)
{
}
void Interpret(char cmd)
{
}
void CreatGraph(GraphType g,File *f)
{
	InitGraph(g);
	fscanf(f,g.vexNum,g.edgeNum);
	for(int i=0;i<g.vexNum;i++)
	{
		fscanf(f,v.name,v.info);
		InsertVex(g,v);
	}
	for(int k=0;k<g.edgeNum;k++)
	{
		fscanf(f,e.ivex,e.jvex,e.length);
		if(e.length) InsertEdge(g,e);
	}
}*/
void printsight(GraphType g,string sight)
{
	//gotoxy(10,10);
	for(int i=0;i<g.vexNum;i++)
	{
		if(sight==g.Adjmulist[i].data.name) 
		{
			cout<<sight<<" infomation is:"<<g.Adjmulist[i].data.info<<endl;
			return;
		}
		else continue;
	} 
	cout<<"wrong!Please reload!";
}
void printpath(int pathlength,PType PathInfo,string sname)
{
	//gotoxy(10,10);
	cout<<"from "<<*sname<<" to "<<PathInfo.vertices[PathInfo.num]<<" 's the shortest path is:";
	/*for(int i=0;i<PathInfo.num;i++)
		cout<<PathInfo.vertices[i]<<"-->";
	cout<<PathInfo.vertices[PathInfo.num];
	cout<<endl<<"though"<<PathInfo.num<<",you need walk length:"<<pathlength<<endl;*/
    cout<<*sname<<"-->";
	for(int i=1;i<PathInfo.num;i++)
	cout<<PathInfo.vertices[i]<<"-->";
	cout<<PathInfo.vertices[PathInfo.num];
	cout<<endl<<"though"<<PathInfo.num<<",you need walk length:"<<pathlength<<endl;
}
void creat(GraphType &g)
{
	InitGraph(g);
	static int v_num=4;
	static int e_num=5;
	VertexType v[4];
	v[0].info="this is our study building!";
	v[0].name="a";
	v[1].info="2";
	v[1].name="b";
	v[2].info="3";
	v[2].name="c";
	v[3].info="4";
	v[3].name="d";
	EdgeType e[5];
	e[0].ivex=0;
	e[0].jvex=1;
	e[0].length=20;
	e[1].ivex=0;
	e[1].jvex=3;
	e[1].length=100;
	e[2].ivex=1;
	e[2].jvex=2;
	e[2].length=20;
	e[3].ivex=0;
	e[3].jvex=2;
	e[3].length=80;
    e[4].ivex=2;
	e[4].jvex=3;
	e[4].length=30;
	for(int i=0;i<v_num;i++)
	{
		InsertVex(g,v[i]);
	}
	for(int k=0;k<e_num;k++)
	{
	    InsertEdge(g,e[k]);
	}
}
void PutInSet(int v,int ss[MAX])
{
	int i=0;
	for(i=0;i<=MAX;i++)
		if(ss[i]==0) break;
    ss[v]=1;
}
status InSet(int w,int ss[MAX])
{
	int i=0;
	for(i=0;i<=MAX;i++)
		if(ss[w]==1)
		{
			return TRUE;
		}
	return FALSE;
}
int minval(GraphType g,int ss[MAX],int dist[MAX])
{
	int min,u,n;
	int i=0;
	while(ss[i]==1) i++;
	min=dist[i];
    u=i;
	n=g.vexNum;
	while(i<n)
	{
		if(ss[i]==1) i++;
		else if(min>dist[i])
		{
			u=i;
			min=dist[i];
		}
		i++;
	}
	return u;
}
void ShortestPath(GraphType g,int st,int nd,int &pathLength,PType &PathInfo)
{
	int dist[MAX];
	PathType path[MAX];
	EdgePtr p,q;
	int adjvex,w;
	int maxint=10000;
	int ss[MAX];
	for(int i=0;i<g.vexNum;i++)
	{
		dist[i]=maxint;
		InitPath(path[i]);
	}
	p=FirstEdge(g,st);
	while(p)
	{
		NextEdge(st,p,adjvex,q);
		dist[adjvex]=p->elem.length;
		InsertPath(path[adjvex],st,adjvex);
		p=q;
	}
	bool found=FALSE;
    for(int k=0;k<=MAX;k++) ss[k]=0;
	ss[st]=1;
	dist[st]=0;
	while(!found)
	{
	    int min=minval(g,ss,dist);
		if(min==nd) found=TRUE;
		else{
			int v=min;
			PutInSet(v,ss);
			p=FirstEdge(g,v);
			while(p)
			{
				NextEdge(v,p,w,q);
				if(!InSet(w,ss)&&(dist[v]+p->elem.length)<dist[w])
				{
					dist[w]=dist[v]+p->elem.length;
					copyPath(path[w],path[v]);
					InsertPath(path[w],v,w);
				}
				p=q;
			}
		}
	}
	 pathLength=dist[nd];
	 OutPath(g,path[nd],PathInfo);
}
void GetShortestPath(GraphType g,string sname,string tname,int &pathLength,PType &PathInfo)
{
	int sv,tv;
	LocateVex(g,sname,sv);
    LocateVex(g,tname,tv);
	ShortestPath(g,sv,tv,pathLength,PathInfo);
}
void main()
{
	clrscr();
	GraphType g;
	int pathLength;
	PType PathInfo;
	InitGraph(g);
	creat(g);
	GetShortestPath(g,"c","b",pathLength,PathInfo);
	//ShortestPath(g,1,0,pathLength,PathInfo);
	printpath(pathLength,PathInfo,"c");
	//printsight(g,"a");
}