#include?“graph.h“
#include?“linklist_path.h“
#include?
#include?
#include?


//創建鄰接表//
void?create_graph（alGraph?*AG）
{
	arcNode?*?p;
	int?ijkweight;
	FILE?*fp;
	fp=fopen（“path.txt““r“）;
	fscanf（fp“%d%d“&AG->vexnum&AG->arcnum）;
	for（i=1;i<=AG->vexnum;i++）
	{
		fscanf（fp“%s“AG->vertices[i].name）;
		AG->vertices[i].id=i;
		AG->vertices[i].firstArc=NULL;
	}

	//權值相同的邊在同一條軌道線上//
	for?（k=1;k<=AG->arcnum;k++）
	{
		fscanf（fp“%d?%d?%d“&i&j&weight）;
		p=（arcNode?*）malloc（sizeof（*p））;
		p->adjvex=j;
		p->weight=weight;
		p->nextarc=AG->vertices[i].firstArc;
		AG->vertices[i].firstArc=p;
		p=（arcNode?*）malloc（sizeof（*p））;
		p->adjvex=i;
		p->weight=weight;
		p->nextarc=AG->vertices[j].firstArc;
		AG->vertices[j].firstArc=p;

	}
	fclose（fp）;
}


//根據所給的站名定位到站的號碼//
int?vertex_locate（alGraph?*AGchar?*a）
{
	int?i=1;
	while（strcmp（AG->vertices[i].namea）&&i<=AG->vexnum）
		i++;
	if（i<=AG->vexnum）
		return?i;
	else?return?0;
}


//讀取信息并準備好調用allsearch//
void?search（alGraph?*AG）
{
	char?from[20]to[20];
	int?ft;
	route?*r;
	path_rec?pa;
	int??visited[MAX_VERTEX_NUM]={0};


	create_path（&pa）;//創建保存路徑的鏈表//
	r=（route?*）malloc（sizeof（route））;
	printf（“Please?tell?me?where?you?are:\n“）;
	scanf（“%s“from）;
	printf（“And?then?tell?me?where?you?are?going:\n“）;
	scanf（“%s“to）;
	f=vertex_locate（AGfrom）;
	t=vertex_locate（AGto）;

	if（f==0||t==0）
	{
		printf（“You?may?enter?the?wrong?place!!\nPlease?retry!\n\n\n“）;
		return;
	}
	r->top=1;

	search_all_path（AGr->pathvisitedftr->top&pa）;
	print_path（AG&pa）;


}


//利用深度搜索的遞歸找出所有的路徑//
void?search_all_path（alGraph?*AGint?*path?int?*visitedint?vint?des?int?toppath_rec?*pa）
{
	int?jixyflag;
	arcNode?*p;
	all_path?*pall;
	if（visited[v]）
		return;
	path[top-1]=v;
	if（v==des）
	{
		flag=0;
		for?（x=0;x		{
			for?（y=x+1;y				if（path[x]==path[y]）
					flag=1;
		}

		if（flag==0）
		{
			pall=（all_path?*）malloc（sizeof（all_path））;
			pall->times=0;
			pall->top=top;
			for（i=0;i			{	
				pall->change_point[i]=0;
				pall->path[i]=path[i];
			}
			get_times（AGpall）;
			insert_path（papall）;
		}

	}
	else
		visited[v]=1;
	for（p=AG->vertices[v].firstArc;p;p=p->nextarc）
	{
		j=p->adjvex;
		if（!visited[j]）
			search_all_path（AGpathvisitedjdestop+1pa）;

	}
	visited[v]=0;
}



//輸出路徑//
void?print_path（alGraph?*AGpath_rec?*pa）
{
	int?m=100k;
	all_path?*p;
	for（p=pa->head->next;p!=NULL;p=p->next）
		if（p->times<=m）
			m=p->times;
	for（p=pa->head->next;p!=NULL;p=p->next）
		if（p->times==m）
		{
			printf（“\n\nThis?way?can?be?the?way?best:\n“）;
			for（k=0;k<（p->top）-1;k++）
			{
				if（p->change_point[k]）
					printf（“%s（在此轉乘）---->“AG->vertices[p->path[k]].name）;
				else
					printf（“%s-->“AG->vertices[p->path[k]].name）;
			}
			printf（“%s\n\n“AG->vertices[p->path[（p->top）-1]].name）;
			printf（“You?need

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件???????3637??2011-11-09?21:57??地鐵換乘系統\graph.c

?????文件???????1064??2011-11-05?20:08??地鐵換乘系統\graph.h

?????文件????????451??2011-11-05?20:03??地鐵換乘系統\linklist_path.c

?????文件????????538??2011-11-04?21:10??地鐵換乘系統\linklist_path.h

?????文件????????818??2011-11-09?21:56??地鐵換乘系統\main.c

?????文件???????3079??2011-11-01?20:03??地鐵換乘系統\path.txt

?????目錄??????????0??2012-03-10?09:05??地鐵換乘系統

-----------?---------??----------?-----??----

?????????????????9587????????????????????7