[問(wèn)題描述]

創(chuàng)新互聯(lián)公司是一家專業(yè)從事網(wǎng)站建設(shè)、網(wǎng)絡(luò)營(yíng)銷、小程序設(shè)計(jì)、網(wǎng)站運(yùn)營(yíng)為一體的建站企業(yè)；在網(wǎng)站建設(shè)告別千篇一律，告別似曾相識(shí)，這一次我們重新定義網(wǎng)站建設(shè)，讓您的網(wǎng)站別具一格。成都響應(yīng)式網(wǎng)站建設(shè)公司，實(shí)現(xiàn)全網(wǎng)營(yíng)銷！一站適應(yīng)多終端，一樣的建站，不一樣的體驗(yàn)！

根據(jù)真實(shí)南京公交線路圖，建立南京主要公交線路圖的存儲(chǔ)結(jié)構(gòu)。

[基本要求]

（1）輸入任意兩站點(diǎn)，給出轉(zhuǎn)車次數(shù)最少的乘車路線。

（2）輸入任意兩站點(diǎn)，給出經(jīng)過(guò)站點(diǎn)最少的乘車路線。

這道題的實(shí)際應(yīng)性比較強(qiáng)，要從文件里讀取大量數(shù)據(jù)來(lái)實(shí)現(xiàn)，文件內(nèi)容（部分）如下圖所示：

即使從大量的數(shù)據(jù)中我們也可以看出，這道題還是比較有難度的。 我的解題思路如下：

既然要用圖，首先就應(yīng)該考慮把什么數(shù)據(jù)作為圖上的結(jié)點(diǎn)。既然是對(duì)任意兩個(gè)站點(diǎn)進(jìn)行操作，所以這里的結(jié)點(diǎn)應(yīng)該是各站點(diǎn)。這里我們采用鄰接表的數(shù)據(jù)結(jié)構(gòu)來(lái)構(gòu)建圖，對(duì)每個(gè)站點(diǎn)我們要保存其名稱以及站點(diǎn)編號(hào)（按創(chuàng)建時(shí)候的順序來(lái)編）。第一步當(dāng)然是打開(kāi)文件，打開(kāi)文本文件后，依次讀取每一行數(shù)據(jù)，然后處理數(shù)據(jù)（這一步并不難，但比較繁瑣，需要細(xì)心和耐心）。

以上都是基本操作，接下來(lái)才是需要思考的地方。首先這道題有兩問(wèn)，這兩問(wèn)本質(zhì)上都和求最短路徑有關(guān)，只是“最短路徑”的含義不一樣。第一問(wèn)是指轉(zhuǎn)車次數(shù)最少的距離，而第二問(wèn)是指經(jīng)過(guò)站點(diǎn)最少的距離。所以，我們要?jiǎng)?chuàng)建兩張鄰接表。第一張鄰接表G1，我們把邊定義為：同一條公交線路上的兩點(diǎn)之間存在邊（這里邊的權(quán)值均為1）；第二張鄰接表G2，我們把邊定義為：相鄰兩站之間存在邊。這就是兩個(gè)圖主要的區(qū)別，使用的結(jié)構(gòu)體是一致的，只是在建立鄰接表時(shí)對(duì)邊的處理方式不同。

下面，如何來(lái)求最短路徑？相信大家都會(huì)想到迪杰斯特拉算法，這是求單源最短路徑的一個(gè)很經(jīng)典、應(yīng)用很廣泛的算法（不知道的小伙伴可以去看去我之前的文章，有詳細(xì)解說(shuō)）。這里我們把相鄰點(diǎn)的權(quán)值都視為1，然后用迪杰斯特拉算法就可以求出以任意站點(diǎn)為起始點(diǎn)，到其它站點(diǎn)的最短距離。這個(gè)”最短距離“在第一問(wèn)就是指轉(zhuǎn)車次數(shù)最少的距離，在第二問(wèn)是指經(jīng)過(guò)站點(diǎn)最少的距離。

另外需要注意的一點(diǎn)是：一般的迪杰斯特拉算法只用到三個(gè)輔助數(shù)組，Adjvex 保存從起始站點(diǎn)到達(dá)某站點(diǎn)會(huì)經(jīng)過(guò)的站點(diǎn)編號(hào)；Lowcost 保存從起始站點(diǎn)到某站點(diǎn)的最短距離；Flag 則用來(lái)標(biāo)注某站點(diǎn)是否已被選中（初始化為0）。在這一題中為了求出換乘線路，我又增加了一個(gè) Route 來(lái)保存從起始站點(diǎn)到達(dá)某站點(diǎn)會(huì)經(jīng)過(guò)的路線。

我的代碼如下：

1、創(chuàng)建兩張鄰接表

# include# include# include# include# include# define SIZE 1024
# define NEWSIZE 1024
# define Infinity 100000000   //表示無(wú)限大
using namespace std;
typedef struct SiteArcNode {        //邊的結(jié)點(diǎn)（站點(diǎn)）結(jié)構(gòu)類型
	int adjvex;						//該邊的站點(diǎn)編號(hào)
	int path;						//站點(diǎn)所在的路線
	struct SiteArcNode* nextarc;	//指向下一條邊的指針
}SiteArcNode;
typedef struct SiteVexNode {  //站點(diǎn)結(jié)構(gòu)
	int num;				  //站點(diǎn)編號(hào)（從0開(kāi)始）
	char name[50];            //站點(diǎn)名稱
	SiteArcNode* firstarc;    //指向第一條與該站點(diǎn)有關(guān)的邊的指針
}SiteVexNode;
typedef struct SiteGraph {    //站點(diǎn)的鄰接表結(jié)構(gòu)類型
	SiteVexNode* SVNode;      //定義鄰接表
	int vexnum;			      //站點(diǎn)數(shù)
	int size;                 //鄰接表的大小
}SiteGraph;

//這里的最短距離可以指經(jīng)過(guò)站點(diǎn)最少的距離，也可以指轉(zhuǎn)車次數(shù)最少的距離
int* Route;     //從起始站點(diǎn)到達(dá)某站點(diǎn)會(huì)經(jīng)過(guò)的路線
int* Adjvex;    //從起始站點(diǎn)到達(dá)某站點(diǎn)會(huì)經(jīng)過(guò)的站點(diǎn)編號(hào)
int* Lowcost;   //從起始站點(diǎn)到某站點(diǎn)的最短距離
int* Flag;      //標(biāo)注站點(diǎn)是否已被選中（初始化為0）
void Create(SiteGraph& G1, SiteGraph& G2); //創(chuàng)建兩張圖（G1：連接同一路線上的站點(diǎn)；G2：連接相鄰站點(diǎn)）
void Dijkstra(SiteGraph G1, int v);        //迪杰斯特拉算法求單源最短路線
void Find_Route(SiteGraph G1);             //對(duì)任意兩站點(diǎn)，給出轉(zhuǎn)車次數(shù)最少的乘車路線
void Find_Site(SiteGraph G2);              //對(duì)任意兩站點(diǎn)，給出經(jīng)過(guò)站點(diǎn)最少的乘車路線
void Print_Path(SiteGraph G, int v1, int v2, string s1);  //打印路線

void Create(SiteGraph& G1, SiteGraph& G2)    //創(chuàng)建圖
{
	fstream file;
	char s[1000];
	G1.SVNode = (SiteVexNode*)malloc(SIZE * sizeof(SiteVexNode));
	G2.SVNode = (SiteVexNode*)malloc(SIZE * sizeof(SiteVexNode));
	G1.size = SIZE;
	G2.size = SIZE;
	G1.vexnum = 0;
	G2.vexnum = 0;
	file.open("南京公交線路.txt", ios::in);
	if (file.fail()) {
		cout<< "文件打開(kāi)失敗"<< endl;
		exit(0);
	}
	file.getline(s, 1000);
	while (!file.eof()) {
		int t = 1, a = 0, k = 0;
		vectorM; //保存這條線路上的所有站點(diǎn)編號(hào)
		char site[50];
		for (int i = 0; i< strlen(s); i++) {
			if (s[i] == ' ') {
				t = 0;
			}
			else if (t && (s[i] >= 48 && s[i]<= 57)) {
				a = a * 10 + s[i] - 48;
			}
			else if (!t) {
				//開(kāi)始處理站點(diǎn)數(shù)據(jù)
				if (s[i] == ',') {
					//遇到“,”說(shuō)明一個(gè)站點(diǎn)已輸入完畢，建立該站點(diǎn)的結(jié)點(diǎn)
					site[k] = '\0';
					k = 0;
					int t1 = 1;
					int n;   //當(dāng)前站點(diǎn)的編號(hào)
					for (int j = 0; j< G2.vexnum; j++) {
						//先查看該站點(diǎn)是否已建立頭結(jié)點(diǎn)
						if (strcmp(G2.SVNode[j].name, site) == 0) {
							t1 = 0;  //該站點(diǎn)已建立頭結(jié)點(diǎn)，t1標(biāo)注為0
							n = j;   //n=當(dāng)前站點(diǎn)的編號(hào)
							break;
						}
					}
					if (t1) {
						//該站點(diǎn)未建立頭結(jié)點(diǎn)
						if (G1.size<= G1.vexnum) {
							//根據(jù)點(diǎn)的個(gè)數(shù)動(dòng)態(tài)分配空間
							G1.SVNode = (SiteVexNode*)realloc(G1.SVNode, (G1.size + NEWSIZE) * sizeof(SiteVexNode));
							G1.size += NEWSIZE;
						}
						if (G2.size<= G2.vexnum) {
							//根據(jù)點(diǎn)的個(gè)數(shù)動(dòng)態(tài)分配空間
							G2.SVNode = (SiteVexNode*)realloc(G2.SVNode, (G2.size + NEWSIZE) * sizeof(SiteVexNode));
							G2.size += NEWSIZE;
						}
						strcpy(G1.SVNode[G1.vexnum].name, site); //頭結(jié)點(diǎn)名稱
						strcpy(G2.SVNode[G2.vexnum].name, site); //頭結(jié)點(diǎn)名稱
						G1.SVNode[G1.vexnum].num = G1.vexnum;    //頭結(jié)點(diǎn)編號(hào)
						G2.SVNode[G2.vexnum].num = G2.vexnum;    //頭結(jié)點(diǎn)編號(hào)
						G1.SVNode[G1.vexnum].firstarc = NULL;
						G2.SVNode[G2.vexnum].firstarc = NULL;
						n = G2.vexnum;  //n=當(dāng)前站點(diǎn)的編號(hào)
						G1.vexnum++;
						G2.vexnum++;
					}
					if (!M.empty()) {
						//如果不是這條線路上的第一個(gè)站點(diǎn)
						SiteArcNode* p, * q;
						//不是第一個(gè)站點(diǎn)，G1表要與這條線路上的所有站點(diǎn)建立連接
						for (int j = 0; j< M.size(); j++) {
							//當(dāng)前站點(diǎn)加入到前面所有站點(diǎn)的鏈表中
							p = (SiteArcNode*)malloc(sizeof(SiteArcNode));  //創(chuàng)建一個(gè)用于存放當(dāng)前邊的結(jié)點(diǎn)p
							p->nextarc = NULL;
							p->adjvex = n;
							p->path = a;  //保存這條邊所在的線路
							q = G1.SVNode[M[j]].firstarc;
							//將邊按順序插入到鏈表末尾
							if (q == NULL) {
								G1.SVNode[M[j]].firstarc = p;
							}
							else {
								while (q->nextarc != NULL) {
									q = q->nextarc;
								}
								q->nextarc = p;
							}
							//前面所有站點(diǎn)加入到當(dāng)前站點(diǎn)的鏈表中
							p = (SiteArcNode*)malloc(sizeof(SiteArcNode));  //創(chuàng)建一個(gè)用于存放當(dāng)前邊的結(jié)點(diǎn)p
							p->nextarc = NULL;
							p->adjvex = M[j];
							p->path = a;   //保存這條邊所在的線路
							q = G1.SVNode[n].firstarc;  //前一個(gè)站點(diǎn)加入到當(dāng)前站點(diǎn)的鏈表中
							//將邊按順序插入到鏈表末尾
							if (q == NULL) {
								G1.SVNode[n].firstarc = p;
							}
							else {
								while (q->nextarc != NULL) {
									q = q->nextarc;
								}
								q->nextarc = p;
							}
						}
						//不是第一個(gè)站點(diǎn)，G2表要與前一個(gè)站點(diǎn)建立連接
						int m = M[M.size() - 1];
						p = (SiteArcNode*)malloc(sizeof(SiteArcNode));  //創(chuàng)建一個(gè)用于存放當(dāng)前邊的結(jié)點(diǎn)p
						p->nextarc = NULL;
						p->adjvex = n;
						p->path = a;
						q = G2.SVNode[m].firstarc;  //當(dāng)前站點(diǎn)加入到前一個(gè)站點(diǎn)的鏈表中
						//將邊按順序插入到鏈表末尾
						if (q == NULL) {
							G2.SVNode[m].firstarc = p;
						}
						else {
							while (q->nextarc != NULL) {
								q = q->nextarc;
							}
							q->nextarc = p;
						}
						p = (SiteArcNode*)malloc(sizeof(SiteArcNode));  //創(chuàng)建一個(gè)用于存放當(dāng)前邊的結(jié)點(diǎn)p
						p->nextarc = NULL;
						p->adjvex = m;
						p->path = a;
						q = G2.SVNode[n].firstarc;  //前一個(gè)站點(diǎn)加入到當(dāng)前站點(diǎn)的鏈表中
						//將邊按順序插入到鏈表末尾
						if (q == NULL) {
							G2.SVNode[n].firstarc = p;
						}
						else {
							while (q->nextarc != NULL) {
								q = q->nextarc;
							}
							q->nextarc = p;
						}
					}
					M.push_back(n);
				}
				else {
					site[k] = s[i];
					k++;
				}
			}
		}
		file.getline(s, 1000);
	}
	file.close();
}

2、求解問(wèn)題1和問(wèn)題2

void Dijkstra(SiteGraph G, int v)  //迪杰斯特拉算法求單源最短路線
{
	Lowcost[v] = 0;          //初始站點(diǎn)到初始站點(diǎn)的距離為0
	Flag[v] = 1;             //標(biāo)注初始點(diǎn)
	int num = 1;             //記錄目前被選中的站點(diǎn)數(shù)目
	SiteArcNode* p;
	while (num< G.vexnum) {
		p = G.SVNode[v].firstarc;  //p為新選中的點(diǎn)的第一個(gè)鄰接點(diǎn)
		while (p != NULL) {
			//由于新點(diǎn)加入，更新起始點(diǎn)與其余未被選中的頂點(diǎn)之間的距離
			if (!Flag[p->adjvex] && Lowcost[p->adjvex] >Lowcost[v] + 1) {
				Lowcost[p->adjvex] = Lowcost[v] + 1;
				Adjvex[p->adjvex] = v;
				Route[p->adjvex] = p->path;  //保存該站點(diǎn)所在的路線
			}
			p = p->nextarc;
		}
		int min = Infinity;
		for (int i = 1; i<= G.vexnum; i++) {
			//從未選擇的站點(diǎn)中找下一個(gè)與起始站點(diǎn)距離最近的站點(diǎn)
			if (!Flag[i] && Lowcost[i]< min) {
				min = Lowcost[i];
				v = i;               //更新v為目前與起始站點(diǎn)距離最近的站點(diǎn)
			}
		}
		Flag[v] = 1;             //標(biāo)記新選中的站點(diǎn)
		num++;                   //目前被選中的站點(diǎn)數(shù)目+1
	}
}

void Print_Path(SiteGraph G, int v1, int v2, string s1)   //打印路線
{
	cout<< "路徑為："<< endl;
	int j = v2;
	vectorPath;
	while (j != v1) {
		Path.push_back(j);
		j = Adjvex[j];
	}
	int k = Route[Path[Path.size() - 1]];
	cout<< k<< "路："<< s1;
	for (int i = Path.size() - 1; i >= 0; i--) {
		if (Route[Path[i]] != k) {
			k = Route[Path[i]];
			cout<< "\n換乘到"<< k<< "路："<< G.SVNode[Path[i + 1]].name;
		}
		cout<< "->"<< G.SVNode[Path[i]].name;
	}
	cout<< endl;
}

void Find_Route(SiteGraph G)     //對(duì)任意兩站點(diǎn)，給出轉(zhuǎn)車次數(shù)最少的乘車路線
{
	string s1, s2;
	int v1, v2;
	cout<< "請(qǐng)輸入第一個(gè)站點(diǎn)：";
	cin >>s1;
	cout<< "請(qǐng)輸入第二個(gè)站點(diǎn)：";
	cin >>s2;
	for (int i = 0; i< G.vexnum; i++) {
		if (G.SVNode[i].name == s1) {
			v1 = i;
		}
		if (G.SVNode[i].name == s2) {
			v2 = i;
		}
	}
	for (int i = 1; i<= G.vexnum; i++) {
		//初始化
		Adjvex[i] = v1;
		Route[i] = 0;
		Lowcost[i] = Infinity;
		Flag[i] = 0;
	}
	Dijkstra(G, v1);   //求從站點(diǎn)v1出發(fā)到站點(diǎn)v2的換乘次數(shù)最少的乘車路線
	cout<< endl;
	cout<< s1<< " 到 "<< s2<< " 的換乘次數(shù)最少為"<< Lowcost[v2] - 1<< "  ";  //換乘次數(shù)要減1
	//輸出起始點(diǎn)到站點(diǎn)v2的最少轉(zhuǎn)車路徑
	Print_Path(G, v1, v2, s1);
}

void Find_Site(SiteGraph G)      //對(duì)任意兩站點(diǎn)，給出經(jīng)過(guò)站點(diǎn)最少的乘車路線
{
	string s1, s2;
	int v1, v2;
	cout<< "請(qǐng)輸入第一個(gè)站點(diǎn)：";
	cin >>s1;
	cout<< "請(qǐng)輸入第二個(gè)站點(diǎn)：";
	cin >>s2;
	for (int i = 0; i< G.vexnum; i++) {
		if (G.SVNode[i].name == s1) {
			v1 = i;
		}
		if (G.SVNode[i].name == s2) {
			v2 = i;
		}
	}
	for (int i = 1; i<= G.vexnum; i++) {
		//初始化
		Adjvex[i] = v1;
		Route[i] = 0;
		Lowcost[i] = Infinity;
		Flag[i] = 0;
	}
	Dijkstra(G, v1);   //求從站點(diǎn)v1出發(fā)到站點(diǎn)v2的經(jīng)過(guò)站點(diǎn)最少的乘車路線
	//輸出起始站點(diǎn)到站點(diǎn)v2的最短距離
	cout<< endl;
	cout<< s1<< " 到 "<< s2<< " 的經(jīng)過(guò)站點(diǎn)次數(shù)最少為"<< Lowcost[v2] + 1<< "  ";
	//輸出起始點(diǎn)到站點(diǎn)v2的最少轉(zhuǎn)車路徑
	Print_Path(G, v1, v2, s1);
}

全部代碼：

# include# include# include# include# include# define SIZE 1024
# define NEWSIZE 1024
# define Infinity 100000000   //表示無(wú)限大
using namespace std;
typedef struct SiteArcNode {        //邊的結(jié)點(diǎn)（站點(diǎn)）結(jié)構(gòu)類型
	int adjvex;						//該邊的站點(diǎn)編號(hào)
	int path;						//站點(diǎn)所在的路線
	struct SiteArcNode* nextarc;	//指向下一條邊的指針
}SiteArcNode;
typedef struct SiteVexNode {  //站點(diǎn)結(jié)構(gòu)
	int num;				  //站點(diǎn)編號(hào)（從0開(kāi)始）
	char name[50];            //站點(diǎn)名稱
	SiteArcNode* firstarc;    //指向第一條與該站點(diǎn)有關(guān)的邊的指針
}SiteVexNode;
typedef struct SiteGraph {    //站點(diǎn)的鄰接表結(jié)構(gòu)類型
	SiteVexNode* SVNode;      //定義鄰接表
	int vexnum;			      //站點(diǎn)數(shù)
	int size;                 //鄰接表的大小
}SiteGraph;

//這里的最短距離可以指經(jīng)過(guò)站點(diǎn)最少的距離，也可以指轉(zhuǎn)車次數(shù)最少的距離
int* Route;     //從起始站點(diǎn)到達(dá)某站點(diǎn)會(huì)經(jīng)過(guò)的路線
int* Adjvex;    //從起始站點(diǎn)到達(dá)某站點(diǎn)會(huì)經(jīng)過(guò)的站點(diǎn)編號(hào)
int* Lowcost;   //從起始站點(diǎn)到某站點(diǎn)的最短距離
int* Flag;      //標(biāo)注站點(diǎn)是否已被選中（初始化為0）
void Create(SiteGraph& G1, SiteGraph& G2); //創(chuàng)建兩張圖（G1：連接同一路線上的站點(diǎn)；G2：連接相鄰站點(diǎn)）
void Dijkstra(SiteGraph G1, int v);        //迪杰斯特拉算法求單源最短路線
void Find_Route(SiteGraph G1);             //對(duì)任意兩站點(diǎn)，給出轉(zhuǎn)車次數(shù)最少的乘車路線
void Find_Site(SiteGraph G2);              //對(duì)任意兩站點(diǎn)，給出經(jīng)過(guò)站點(diǎn)最少的乘車路線
void Print_Path(SiteGraph G, int v1, int v2, string s1);  //打印路線

int main()
{
	SiteGraph G1, G2;
	Create(G1, G2);
	//動(dòng)態(tài)創(chuàng)建輔助數(shù)組
	Adjvex = (int*)malloc((G1.vexnum + 10) * sizeof(int));
	Route = (int*)malloc((G1.vexnum + 10) * sizeof(int));
	Lowcost = (int*)malloc((G1.vexnum + 10) * sizeof(int));
	Flag = (int*)malloc((G1.vexnum + 10) * sizeof(int));
	cout<< "（1）輸入任意兩站點(diǎn)，給出轉(zhuǎn)車次數(shù)最少的乘車路線"<< endl;
	Find_Route(G1);
	cout<< endl;
	cout<< "*********************************************************************************\n";
	cout<< endl;
	cout<< "（2）輸入任意兩站點(diǎn)，給出經(jīng)過(guò)站點(diǎn)最少的乘車路線"<< endl;
	Find_Site(G2);
	return 0;
}

void Create(SiteGraph& G1, SiteGraph& G2)    //創(chuàng)建圖
{
	fstream file;
	char s[1000];
	G1.SVNode = (SiteVexNode*)malloc(SIZE * sizeof(SiteVexNode));
	G2.SVNode = (SiteVexNode*)malloc(SIZE * sizeof(SiteVexNode));
	G1.size = SIZE;
	G2.size = SIZE;
	G1.vexnum = 0;
	G2.vexnum = 0;
	file.open("南京公交線路.txt", ios::in);
	if (file.fail()) {
		cout<< "文件打開(kāi)失敗"<< endl;
		exit(0);
	}
	file.getline(s, 1000);
	while (!file.eof()) {
		int t = 1, a = 0, k = 0;
		vectorM; //保存這條線路上的所有站點(diǎn)編號(hào)
		char site[50];
		for (int i = 0; i< strlen(s); i++) {
			if (s[i] == ' ') {
				t = 0;
			}
			else if (t && (s[i] >= 48 && s[i]<= 57)) {
				a = a * 10 + s[i] - 48;
			}
			else if (!t) {
				//開(kāi)始處理站點(diǎn)數(shù)據(jù)
				if (s[i] == ',') {
					//遇到“,”說(shuō)明一個(gè)站點(diǎn)已輸入完畢，建立該站點(diǎn)的結(jié)點(diǎn)
					site[k] = '\0';
					k = 0;
					int t1 = 1;
					int n;   //當(dāng)前站點(diǎn)的編號(hào)
					for (int j = 0; j< G2.vexnum; j++) {
						//先查看該站點(diǎn)是否已建立頭結(jié)點(diǎn)
						if (strcmp(G2.SVNode[j].name, site) == 0) {
							t1 = 0;  //該站點(diǎn)已建立頭結(jié)點(diǎn)，t1標(biāo)注為0
							n = j;   //n=當(dāng)前站點(diǎn)的編號(hào)
							break;
						}
					}
					if (t1) {
						//該站點(diǎn)未建立頭結(jié)點(diǎn)
						if (G1.size<= G1.vexnum) {
							//根據(jù)點(diǎn)的個(gè)數(shù)動(dòng)態(tài)分配空間
							G1.SVNode = (SiteVexNode*)realloc(G1.SVNode, (G1.size + NEWSIZE) * sizeof(SiteVexNode));
							G1.size += NEWSIZE;
						}
						if (G2.size<= G2.vexnum) {
							//根據(jù)點(diǎn)的個(gè)數(shù)動(dòng)態(tài)分配空間
							G2.SVNode = (SiteVexNode*)realloc(G2.SVNode, (G2.size + NEWSIZE) * sizeof(SiteVexNode));
							G2.size += NEWSIZE;
						}
						strcpy(G1.SVNode[G1.vexnum].name, site); //頭結(jié)點(diǎn)名稱
						strcpy(G2.SVNode[G2.vexnum].name, site); //頭結(jié)點(diǎn)名稱
						G1.SVNode[G1.vexnum].num = G1.vexnum;    //頭結(jié)點(diǎn)編號(hào)
						G2.SVNode[G2.vexnum].num = G2.vexnum;    //頭結(jié)點(diǎn)編號(hào)
						G1.SVNode[G1.vexnum].firstarc = NULL;
						G2.SVNode[G2.vexnum].firstarc = NULL;
						n = G2.vexnum;  //n=當(dāng)前站點(diǎn)的編號(hào)
						G1.vexnum++;
						G2.vexnum++;
					}
					if (!M.empty()) {
						//如果不是這條線路上的第一個(gè)站點(diǎn)
						SiteArcNode* p, * q;
						//不是第一個(gè)站點(diǎn)，G1表要與這條線路上的所有站點(diǎn)建立連接
						for (int j = 0; j< M.size(); j++) {
							//當(dāng)前站點(diǎn)加入到前面所有站點(diǎn)的鏈表中
							p = (SiteArcNode*)malloc(sizeof(SiteArcNode));  //創(chuàng)建一個(gè)用于存放當(dāng)前邊的結(jié)點(diǎn)p
							p->nextarc = NULL;
							p->adjvex = n;
							p->path = a;  //保存這條邊所在的線路
							q = G1.SVNode[M[j]].firstarc;
							//將邊按順序插入到鏈表末尾
							if (q == NULL) {
								G1.SVNode[M[j]].firstarc = p;
							}
							else {
								while (q->nextarc != NULL) {
									q = q->nextarc;
								}
								q->nextarc = p;
							}
							//前面所有站點(diǎn)加入到當(dāng)前站點(diǎn)的鏈表中
							p = (SiteArcNode*)malloc(sizeof(SiteArcNode));  //創(chuàng)建一個(gè)用于存放當(dāng)前邊的結(jié)點(diǎn)p
							p->nextarc = NULL;
							p->adjvex = M[j];
							p->path = a;   //保存這條邊所在的線路
							q = G1.SVNode[n].firstarc;  //前一個(gè)站點(diǎn)加入到當(dāng)前站點(diǎn)的鏈表中
							//將邊按順序插入到鏈表末尾
							if (q == NULL) {
								G1.SVNode[n].firstarc = p;
							}
							else {
								while (q->nextarc != NULL) {
									q = q->nextarc;
								}
								q->nextarc = p;
							}
						}
						//不是第一個(gè)站點(diǎn)，G2表要與前一個(gè)站點(diǎn)建立連接
						int m = M[M.size() - 1];
						p = (SiteArcNode*)malloc(sizeof(SiteArcNode));  //創(chuàng)建一個(gè)用于存放當(dāng)前邊的結(jié)點(diǎn)p
						p->nextarc = NULL;
						p->adjvex = n;
						p->path = a;
						q = G2.SVNode[m].firstarc;  //當(dāng)前站點(diǎn)加入到前一個(gè)站點(diǎn)的鏈表中
						//將邊按順序插入到鏈表末尾
						if (q == NULL) {
							G2.SVNode[m].firstarc = p;
						}
						else {
							while (q->nextarc != NULL) {
								q = q->nextarc;
							}
							q->nextarc = p;
						}
						p = (SiteArcNode*)malloc(sizeof(SiteArcNode));  //創(chuàng)建一個(gè)用于存放當(dāng)前邊的結(jié)點(diǎn)p
						p->nextarc = NULL;
						p->adjvex = m;
						p->path = a;
						q = G2.SVNode[n].firstarc;  //前一個(gè)站點(diǎn)加入到當(dāng)前站點(diǎn)的鏈表中
						//將邊按順序插入到鏈表末尾
						if (q == NULL) {
							G2.SVNode[n].firstarc = p;
						}
						else {
							while (q->nextarc != NULL) {
								q = q->nextarc;
							}
							q->nextarc = p;
						}
					}
					M.push_back(n);
				}
				else {
					site[k] = s[i];
					k++;
				}
			}
		}
		file.getline(s, 1000);
	}
	file.close();
}

void Dijkstra(SiteGraph G, int v)  //迪杰斯特拉算法求單源最短路線
{
	Lowcost[v] = 0;          //初始站點(diǎn)到初始站點(diǎn)的距離為0
	Flag[v] = 1;             //標(biāo)注初始點(diǎn)
	int num = 1;             //記錄目前被選中的站點(diǎn)數(shù)目
	SiteArcNode* p;
	while (num< G.vexnum) {
		p = G.SVNode[v].firstarc;  //p為新選中的點(diǎn)的第一個(gè)鄰接點(diǎn)
		while (p != NULL) {
			//由于新點(diǎn)加入，更新起始點(diǎn)與其余未被選中的頂點(diǎn)之間的距離
			if (!Flag[p->adjvex] && Lowcost[p->adjvex] >Lowcost[v] + 1) {
				Lowcost[p->adjvex] = Lowcost[v] + 1;
				Adjvex[p->adjvex] = v;
				Route[p->adjvex] = p->path;  //保存該站點(diǎn)所在的路線
			}
			p = p->nextarc;
		}
		int min = Infinity;
		for (int i = 1; i<= G.vexnum; i++) {
			//從未選擇的站點(diǎn)中找下一個(gè)與起始站點(diǎn)距離最近的站點(diǎn)
			if (!Flag[i] && Lowcost[i]< min) {
				min = Lowcost[i];
				v = i;               //更新v為目前與起始站點(diǎn)距離最近的站點(diǎn)
			}
		}
		Flag[v] = 1;             //標(biāo)記新選中的站點(diǎn)
		num++;                   //目前被選中的站點(diǎn)數(shù)目+1
	}
}

void Print_Path(SiteGraph G, int v1, int v2, string s1)   //打印路線
{
	cout<< "路徑為："<< endl;
	int j = v2;
	vectorPath;
	while (j != v1) {
		Path.push_back(j);
		j = Adjvex[j];
	}
	int k = Route[Path[Path.size() - 1]];
	cout<< k<< "路："<< s1;
	for (int i = Path.size() - 1; i >= 0; i--) {
		if (Route[Path[i]] != k) {
			k = Route[Path[i]];
			cout<< "\n換乘到"<< k<< "路："<< G.SVNode[Path[i + 1]].name;
		}
		cout<< "->"<< G.SVNode[Path[i]].name;
	}
	cout<< endl;
}

void Find_Route(SiteGraph G)     //對(duì)任意兩站點(diǎn)，給出轉(zhuǎn)車次數(shù)最少的乘車路線
{
	string s1, s2;
	int v1, v2;
	cout<< "請(qǐng)輸入第一個(gè)站點(diǎn)：";
	cin >>s1;
	cout<< "請(qǐng)輸入第二個(gè)站點(diǎn)：";
	cin >>s2;
	for (int i = 0; i< G.vexnum; i++) {
		if (G.SVNode[i].name == s1) {
			v1 = i;
		}
		if (G.SVNode[i].name == s2) {
			v2 = i;
		}
	}
	for (int i = 1; i<= G.vexnum; i++) {
		//初始化
		Adjvex[i] = v1;
		Route[i] = 0;
		Lowcost[i] = Infinity;
		Flag[i] = 0;
	}
	Dijkstra(G, v1);   //求從站點(diǎn)v1出發(fā)到站點(diǎn)v2的換乘次數(shù)最少的乘車路線
	cout<< endl;
	cout<< s1<< " 到 "<< s2<< " 的換乘次數(shù)最少為"<< Lowcost[v2] - 1<< "  ";  //換乘次數(shù)要減1
	//輸出起始點(diǎn)到站點(diǎn)v2的最少轉(zhuǎn)車路徑
	Print_Path(G, v1, v2, s1);
}

void Find_Site(SiteGraph G)      //對(duì)任意兩站點(diǎn)，給出經(jīng)過(guò)站點(diǎn)最少的乘車路線
{
	string s1, s2;
	int v1, v2;
	cout<< "請(qǐng)輸入第一個(gè)站點(diǎn)：";
	cin >>s1;
	cout<< "請(qǐng)輸入第二個(gè)站點(diǎn)：";
	cin >>s2;
	for (int i = 0; i< G.vexnum; i++) {
		if (G.SVNode[i].name == s1) {
			v1 = i;
		}
		if (G.SVNode[i].name == s2) {
			v2 = i;
		}
	}
	for (int i = 1; i<= G.vexnum; i++) {
		//初始化
		Adjvex[i] = v1;
		Route[i] = 0;
		Lowcost[i] = Infinity;
		Flag[i] = 0;
	}
	Dijkstra(G, v1);   //求從站點(diǎn)v1出發(fā)到站點(diǎn)v2的經(jīng)過(guò)站點(diǎn)最少的乘車路線
	//輸出起始站點(diǎn)到站點(diǎn)v2的最短距離
	cout<< endl;
	cout<< s1<< " 到 "<< s2<< " 的經(jīng)過(guò)站點(diǎn)次數(shù)最少為"<< Lowcost[v2] + 1<< "  ";
	//輸出起始點(diǎn)到站點(diǎn)v2的最少轉(zhuǎn)車路徑
	Print_Path(G, v1, v2, s1);
}

運(yùn)行結(jié)果：

（1）輸入任意兩站點(diǎn)，給出轉(zhuǎn)車次數(shù)最少的乘車路線
請(qǐng)輸入第一個(gè)站點(diǎn)：白馬公園站
請(qǐng)輸入第二個(gè)站點(diǎn)：櫻花路站

白馬公園站 到 櫻花路站 的換乘次數(shù)最少為1  路徑為：
20路：白馬公園站->北京東路九華山站
換乘到11路：北京東路九華山站->櫻花路站

*********************************************************************************

（2）輸入任意兩站點(diǎn)，給出經(jīng)過(guò)站點(diǎn)最少的乘車路線
請(qǐng)輸入第一個(gè)站點(diǎn)：白馬公園站
請(qǐng)輸入第二個(gè)站點(diǎn)：櫻花路站

白馬公園站 到 櫻花路站 的經(jīng)過(guò)站點(diǎn)次數(shù)最少為8  路徑為：
20路：白馬公園站->太平門(mén)站
換乘到11路：太平門(mén)站->板倉(cāng)街崗子村站
換乘到6路：板倉(cāng)街崗子村站->板倉(cāng)村站->板倉(cāng)街花園路站->櫻駝村站->蔣王廟站->櫻花路站

這里我采用的數(shù)據(jù)結(jié)構(gòu)是鄰接表，當(dāng)然也可以使用鄰接矩陣，基本方法是不變的。不過(guò)使用鄰接矩陣會(huì)浪費(fèi)大量的空間，運(yùn)行時(shí)也會(huì)比鄰接表慢，所以建議使用鄰接表。這道題雖然相對(duì)復(fù)雜，但貼近生活實(shí)際，對(duì)于大家熟悉和應(yīng)用迪杰斯特拉算法有很大的幫助。

以上便是我對(duì)這道題的思考，很高興能與大家分享。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

文章名稱：公交線路提示(課設(shè)）-創(chuàng)新互聯(lián)
本文鏈接：http://www.rwnh.cn/article44/ephee.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供外貿(mào)建站、ChatGPT、網(wǎng)站收錄、虛擬主機(jī)、關(guān)鍵詞優(yōu)化、網(wǎng)站改版

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)