[問題描述]
根據(jù)真實南京公交線路圖，建立南京主要公交線路圖的存儲結(jié)構(gòu)。
[基本要求]
（1）輸入任意兩站點，給出轉(zhuǎn)車次數(shù)最少的乘車路線。
（2）輸入任意兩站點，給出經(jīng)過站點最少的乘車路線。
這道題的實際應(yīng)性比較強，要從文件里讀取大量數(shù)據(jù)來實現(xiàn)，文件內(nèi)容（部分）如下圖所示：
即使從大量的數(shù)據(jù)中我們也可以看出，這道題還是比較有難度的。 我的解題思路如下：
既然要用圖，首先就應(yīng)該考慮把什么數(shù)據(jù)作為圖上的結(jié)點。既然是對任意兩個站點進行操作，所以這里的結(jié)點應(yīng)該是各站點。這里我們采用鄰接表的數(shù)據(jù)結(jié)構(gòu)來構(gòu)建圖，對每個站點我們要保存其名稱以及站點編號（按創(chuàng)建時候的順序來編）。第一步當(dāng)然是打開文件，打開文本文件后，依次讀取每一行數(shù)據(jù)，然后處理數(shù)據(jù)（這一步并不難，但比較繁瑣，需要細(xì)心和耐心）。
以上都是基本操作，接下來才是需要思考的地方。首先這道題有兩問，這兩問本質(zhì)上都和求最短路徑有關(guān)，只是“最短路徑”的含義不一樣。第一問是指轉(zhuǎn)車次數(shù)最少的距離，而第二問是指經(jīng)過站點最少的距離。所以，我們要創(chuàng)建兩張鄰接表。第一張鄰接表G1，我們把邊定義為：同一條公交線路上的兩點之間存在邊（這里邊的權(quán)值均為1）；第二張鄰接表G2，我們把邊定義為：相鄰兩站之間存在邊。這就是兩個圖主要的區(qū)別，使用的結(jié)構(gòu)體是一致的，只是在建立鄰接表時對邊的處理方式不同。
下面，如何來求最短路徑？相信大家都會想到迪杰斯特拉算法，這是求單源最短路徑的一個很經(jīng)典、應(yīng)用很廣泛的算法（不知道的小伙伴可以去看去我之前的文章，有詳細(xì)解說）。這里我們把相鄰點的權(quán)值都視為1，然后用迪杰斯特拉算法就可以求出以任意站點為起始點，到其它站點的最短距離。這個”最短距離“在第一問就是指轉(zhuǎn)車次數(shù)最少的距離，在第二問是指經(jīng)過站點最少的距離。
另外需要注意的一點是：一般的迪杰斯特拉算法只用到三個輔助數(shù)組，Adjvex 保存從起始站點到達(dá)某站點會經(jīng)過的站點編號；Lowcost 保存從起始站點到某站點的最短距離；Flag 則用來標(biāo)注某站點是否已被選中（初始化為0）。在這一題中為了求出換乘線路，我又增加了一個 Route 來保存從起始站點到達(dá)某站點會經(jīng)過的路線。
我的代碼如下：
1、創(chuàng)建兩張鄰接表
重慶分公司
重慶分公司
# include# include# include# include# include# define SIZE 1024
# define NEWSIZE 1024
# define Infinity 100000000 //表示無限大
using namespace std;
typedef struct SiteArcNode { //邊的結(jié)點（站點）結(jié)構(gòu)類型
int adjvex; //該邊的站點編號
int path; //站點所在的路線
struct SiteArcNode* nextarc; //指向下一條邊的指針
}SiteArcNode;
typedef struct SiteVexNode { //站點結(jié)構(gòu)
int num; //站點編號（從0開始）
char name[50]; //站點名稱
SiteArcNode* firstarc; //指向第一條與該站點有關(guān)的邊的指針
}SiteVexNode;
typedef struct SiteGraph { //站點的鄰接表結(jié)構(gòu)類型
SiteVexNode* SVNode; //定義鄰接表
int vexnum; //站點數(shù)
int size; //鄰接表的大小
}SiteGraph;
//這里的最短距離可以指經(jīng)過站點最少的距離，也可以指轉(zhuǎn)車次數(shù)最少的距離
int* Route; //從起始站點到達(dá)某站點會經(jīng)過的路線
int* Adjvex; //從起始站點到達(dá)某站點會經(jīng)過的站點編號
int* Lowcost; //從起始站點到某站點的最短距離
int* Flag; //標(biāo)注站點是否已被選中（初始化為0）
void Create(SiteGraph& G1, SiteGraph& G2); //創(chuàng)建兩張圖（G1：連接同一路線上的站點；G2：連接相鄰站點）
void Dijkstra(SiteGraph G1, int v); //迪杰斯特拉算法求單源最短路線
void Find_Route(SiteGraph G1); //對任意兩站點，給出轉(zhuǎn)車次數(shù)最少的乘車路線
void Find_Site(SiteGraph G2); //對任意兩站點，給出經(jīng)過站點最少的乘車路線
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<< "文件打開失敗"<< endl;
exit(0);
}
file.getline(s, 1000);
while (!file.eof()) {
int t = 1, a = 0, k = 0;
vectorM; //保存這條線路上的所有站點編號
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) {
//開始處理站點數(shù)據(jù)
if (s[i] == ',') {
//遇到“,”說明一個站點已輸入完畢，建立該站點的結(jié)點
site[k] = '\0';
k = 0;
int t1 = 1;
int n; //當(dāng)前站點的編號
for (int j = 0; j< G2.vexnum; j++) {
//先查看該站點是否已建立頭結(jié)點
if (strcmp(G2.SVNode[j].name, site) == 0) {
t1 = 0; //該站點已建立頭結(jié)點，t1標(biāo)注為0
n = j; //n=當(dāng)前站點的編號
break;
}
}
if (t1) {
//該站點未建立頭結(jié)點
if (G1.size<= G1.vexnum) {
//根據(jù)點的個數(shù)動態(tài)分配空間
G1.SVNode = (SiteVexNode*)realloc(G1.SVNode, (G1.size + NEWSIZE) * sizeof(SiteVexNode));
G1.size += NEWSIZE;
}
if (G2.size<= G2.vexnum) {
//根據(jù)點的個數(shù)動態(tài)分配空間
G2.SVNode = (SiteVexNode*)realloc(G2.SVNode, (G2.size + NEWSIZE) * sizeof(SiteVexNode));
G2.size += NEWSIZE;
}
strcpy(G1.SVNode[G1.vexnum].name, site); //頭結(jié)點名稱
strcpy(G2.SVNode[G2.vexnum].name, site); //頭結(jié)點名稱
G1.SVNode[G1.vexnum].num = G1.vexnum; //頭結(jié)點編號
G2.SVNode[G2.vexnum].num = G2.vexnum; //頭結(jié)點編號
G1.SVNode[G1.vexnum].firstarc = NULL;
G2.SVNode[G2.vexnum].firstarc = NULL;
n = G2.vexnum; //n=當(dāng)前站點的編號
G1.vexnum++;
G2.vexnum++;
}
if (!M.empty()) {
//如果不是這條線路上的第一個站點
SiteArcNode* p, * q;
//不是第一個站點，G1表要與這條線路上的所有站點建立連接
for (int j = 0; j< M.size(); j++) {
//當(dāng)前站點加入到前面所有站點的鏈表中
p = (SiteArcNode*)malloc(sizeof(SiteArcNode)); //創(chuàng)建一個用于存放當(dāng)前邊的結(jié)點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;
}
//前面所有站點加入到當(dāng)前站點的鏈表中
p = (SiteArcNode*)malloc(sizeof(SiteArcNode)); //創(chuàng)建一個用于存放當(dāng)前邊的結(jié)點p
p->nextarc = NULL;
p->adjvex = M[j];
p->path = a; //保存這條邊所在的線路
q = G1.SVNode[n].firstarc; //前一個站點加入到當(dāng)前站點的鏈表中
//將邊按順序插入到鏈表末尾
if (q == NULL) {
G1.SVNode[n].firstarc = p;
}
else {
while (q->nextarc != NULL) {
q = q->nextarc;
}
q->nextarc = p;
}
}
//不是第一個站點，G2表要與前一個站點建立連接
int m = M[M.size() - 1];
p = (SiteArcNode*)malloc(sizeof(SiteArcNode)); //創(chuàng)建一個用于存放當(dāng)前邊的結(jié)點p
p->nextarc = NULL;
p->adjvex = n;
p->path = a;
q = G2.SVNode[m].firstarc; //當(dāng)前站點加入到前一個站點的鏈表中
//將邊按順序插入到鏈表末尾
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)建一個用于存放當(dāng)前邊的結(jié)點p
p->nextarc = NULL;
p->adjvex = m;
p->path = a;
q = G2.SVNode[n].firstarc; //前一個站點加入到當(dāng)前站點的鏈表中
//將邊按順序插入到鏈表末尾
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、求解問題1和問題2
void Dijkstra(SiteGraph G, int v) //迪杰斯特拉算法求單源最短路線
{
Lowcost[v] = 0; //初始站點到初始站點的距離為0
Flag[v] = 1; //標(biāo)注初始點
int num = 1; //記錄目前被選中的站點數(shù)目
SiteArcNode* p;
while (num< G.vexnum) {
p = G.SVNode[v].firstarc; //p為新選中的點的第一個鄰接點
while (p != NULL) {
//由于新點加入，更新起始點與其余未被選中的頂點之間的距離
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; //保存該站點所在的路線
}
p = p->nextarc;
}
int min = Infinity;
for (int i = 1; i<= G.vexnum; i++) {
//從未選擇的站點中找下一個與起始站點距離最近的站點
if (!Flag[i] && Lowcost[i]< min) {
min = Lowcost[i];
v = i; //更新v為目前與起始站點距離最近的站點
}
}
Flag[v] = 1; //標(biāo)記新選中的站點
num++; //目前被選中的站點數(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) //對任意兩站點，給出轉(zhuǎn)車次數(shù)最少的乘車路線
{
string s1, s2;
int v1, v2;
cout<< "請輸入第一個站點：";
cin >>s1;
cout<< "請輸入第二個站點：";
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); //求從站點v1出發(fā)到站點v2的換乘次數(shù)最少的乘車路線
cout<< endl;
cout<< s1<< " 到 "<< s2<< " 的換乘次數(shù)最少為"<< Lowcost[v2] - 1<< " "; //換乘次數(shù)要減1
//輸出起始點到站點v2的最少轉(zhuǎn)車路徑
Print_Path(G, v1, v2, s1);
}
void Find_Site(SiteGraph G) //對任意兩站點，給出經(jīng)過站點最少的乘車路線
{
string s1, s2;
int v1, v2;
cout<< "請輸入第一個站點：";
cin >>s1;
cout<< "請輸入第二個站點：";
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); //求從站點v1出發(fā)到站點v2的經(jīng)過站點最少的乘車路線
//輸出起始站點到站點v2的最短距離
cout<< endl;
cout<< s1<< " 到 "<< s2<< " 的經(jīng)過站點次數(shù)最少為"<< Lowcost[v2] + 1<< " ";
//輸出起始點到站點v2的最少轉(zhuǎn)車路徑
Print_Path(G, v1, v2, s1);
} 全部代碼：
# include# include# include# include# include# define SIZE 1024
# define NEWSIZE 1024
# define Infinity 100000000 //表示無限大
using namespace std;
typedef struct SiteArcNode { //邊的結(jié)點（站點）結(jié)構(gòu)類型
int adjvex; //該邊的站點編號
int path; //站點所在的路線
struct SiteArcNode* nextarc; //指向下一條邊的指針
}SiteArcNode;
typedef struct SiteVexNode { //站點結(jié)構(gòu)
int num; //站點編號（從0開始）
char name[50]; //站點名稱
SiteArcNode* firstarc; //指向第一條與該站點有關(guān)的邊的指針
}SiteVexNode;
typedef struct SiteGraph { //站點的鄰接表結(jié)構(gòu)類型
SiteVexNode* SVNode; //定義鄰接表
int vexnum; //站點數(shù)
int size; //鄰接表的大小
}SiteGraph;
//這里的最短距離可以指經(jīng)過站點最少的距離，也可以指轉(zhuǎn)車次數(shù)最少的距離
int* Route; //從起始站點到達(dá)某站點會經(jīng)過的路線
int* Adjvex; //從起始站點到達(dá)某站點會經(jīng)過的站點編號
int* Lowcost; //從起始站點到某站點的最短距離
int* Flag; //標(biāo)注站點是否已被選中（初始化為0）
void Create(SiteGraph& G1, SiteGraph& G2); //創(chuàng)建兩張圖（G1：連接同一路線上的站點；G2：連接相鄰站點）
void Dijkstra(SiteGraph G1, int v); //迪杰斯特拉算法求單源最短路線
void Find_Route(SiteGraph G1); //對任意兩站點，給出轉(zhuǎn)車次數(shù)最少的乘車路線
void Find_Site(SiteGraph G2); //對任意兩站點，給出經(jīng)過站點最少的乘車路線
void Print_Path(SiteGraph G, int v1, int v2, string s1); //打印路線
int main()
{
SiteGraph G1, G2;
Create(G1, G2);
//動態(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）輸入任意兩站點，給出轉(zhuǎn)車次數(shù)最少的乘車路線"<< endl;
Find_Route(G1);
cout<< endl;
cout<< "*********************************************************************************\n";
cout<< endl;
cout<< "（2）輸入任意兩站點，給出經(jīng)過站點最少的乘車路線"<< 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<< "文件打開失敗"<< endl;
exit(0);
}
file.getline(s, 1000);
while (!file.eof()) {
int t = 1, a = 0, k = 0;
vectorM; //保存這條線路上的所有站點編號
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) {
//開始處理站點數(shù)據(jù)
if (s[i] == ',') {
//遇到“,”說明一個站點已輸入完畢，建立該站點的結(jié)點
site[k] = '\0';
k = 0;
int t1 = 1;
int n; //當(dāng)前站點的編號
for (int j = 0; j< G2.vexnum; j++) {
//先查看該站點是否已建立頭結(jié)點
if (strcmp(G2.SVNode[j].name, site) == 0) {
t1 = 0; //該站點已建立頭結(jié)點，t1標(biāo)注為0
n = j; //n=當(dāng)前站點的編號
break;
}
}
if (t1) {
//該站點未建立頭結(jié)點
if (G1.size<= G1.vexnum) {
//根據(jù)點的個數(shù)動態(tài)分配空間
G1.SVNode = (SiteVexNode*)realloc(G1.SVNode, (G1.size + NEWSIZE) * sizeof(SiteVexNode));
G1.size += NEWSIZE;
}
if (G2.size<= G2.vexnum) {
//根據(jù)點的個數(shù)動態(tài)分配空間
G2.SVNode = (SiteVexNode*)realloc(G2.SVNode, (G2.size + NEWSIZE) * sizeof(SiteVexNode));
G2.size += NEWSIZE;
}
strcpy(G1.SVNode[G1.vexnum].name, site); //頭結(jié)點名稱
strcpy(G2.SVNode[G2.vexnum].name, site); //頭結(jié)點名稱
G1.SVNode[G1.vexnum].num = G1.vexnum; //頭結(jié)點編號
G2.SVNode[G2.vexnum].num = G2.vexnum; //頭結(jié)點編號
G1.SVNode[G1.vexnum].firstarc = NULL;
G2.SVNode[G2.vexnum].firstarc = NULL;
n = G2.vexnum; //n=當(dāng)前站點的編號
G1.vexnum++;
G2.vexnum++;
}
if (!M.empty()) {
//如果不是這條線路上的第一個站點
SiteArcNode* p, * q;
//不是第一個站點，G1表要與這條線路上的所有站點建立連接
for (int j = 0; j< M.size(); j++) {
//當(dāng)前站點加入到前面所有站點的鏈表中
p = (SiteArcNode*)malloc(sizeof(SiteArcNode)); //創(chuàng)建一個用于存放當(dāng)前邊的結(jié)點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;
}
//前面所有站點加入到當(dāng)前站點的鏈表中
p = (SiteArcNode*)malloc(sizeof(SiteArcNode)); //創(chuàng)建一個用于存放當(dāng)前邊的結(jié)點p
p->nextarc = NULL;
p->adjvex = M[j];
p->path = a; //保存這條邊所在的線路
q = G1.SVNode[n].firstarc; //前一個站點加入到當(dāng)前站點的鏈表中
//將邊按順序插入到鏈表末尾
if (q == NULL) {
G1.SVNode[n].firstarc = p;
}
else {
while (q->nextarc != NULL) {
q = q->nextarc;
}
q->nextarc = p;
}
}
//不是第一個站點，G2表要與前一個站點建立連接
int m = M[M.size() - 1];
p = (SiteArcNode*)malloc(sizeof(SiteArcNode)); //創(chuàng)建一個用于存放當(dāng)前邊的結(jié)點p
p->nextarc = NULL;
p->adjvex = n;
p->path = a;
q = G2.SVNode[m].firstarc; //當(dāng)前站點加入到前一個站點的鏈表中
//將邊按順序插入到鏈表末尾
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)建一個用于存放當(dāng)前邊的結(jié)點p
p->nextarc = NULL;
p->adjvex = m;
p->path = a;
q = G2.SVNode[n].firstarc; //前一個站點加入到當(dāng)前站點的鏈表中
//將邊按順序插入到鏈表末尾
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; //初始站點到初始站點的距離為0
Flag[v] = 1; //標(biāo)注初始點
int num = 1; //記錄目前被選中的站點數(shù)目
SiteArcNode* p;
while (num< G.vexnum) {
p = G.SVNode[v].firstarc; //p為新選中的點的第一個鄰接點
while (p != NULL) {
//由于新點加入，更新起始點與其余未被選中的頂點之間的距離
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; //保存該站點所在的路線
}
p = p->nextarc;
}
int min = Infinity;
for (int i = 1; i<= G.vexnum; i++) {
//從未選擇的站點中找下一個與起始站點距離最近的站點
if (!Flag[i] && Lowcost[i]< min) {
min = Lowcost[i];
v = i; //更新v為目前與起始站點距離最近的站點
}
}
Flag[v] = 1; //標(biāo)記新選中的站點
num++; //目前被選中的站點數(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) //對任意兩站點，給出轉(zhuǎn)車次數(shù)最少的乘車路線
{
string s1, s2;
int v1, v2;
cout<< "請輸入第一個站點：";
cin >>s1;
cout<< "請輸入第二個站點：";
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); //求從站點v1出發(fā)到站點v2的換乘次數(shù)最少的乘車路線
cout<< endl;
cout<< s1<< " 到 "<< s2<< " 的換乘次數(shù)最少為"<< Lowcost[v2] - 1<< " "; //換乘次數(shù)要減1
//輸出起始點到站點v2的最少轉(zhuǎn)車路徑
Print_Path(G, v1, v2, s1);
}
void Find_Site(SiteGraph G) //對任意兩站點，給出經(jīng)過站點最少的乘車路線
{
string s1, s2;
int v1, v2;
cout<< "請輸入第一個站點：";
cin >>s1;
cout<< "請輸入第二個站點：";
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); //求從站點v1出發(fā)到站點v2的經(jīng)過站點最少的乘車路線
//輸出起始站點到站點v2的最短距離
cout<< endl;
cout<< s1<< " 到 "<< s2<< " 的經(jīng)過站點次數(shù)最少為"<< Lowcost[v2] + 1<< " ";
//輸出起始點到站點v2的最少轉(zhuǎn)車路徑
Print_Path(G, v1, v2, s1);
} 運行結(jié)果：
（1）輸入任意兩站點，給出轉(zhuǎn)車次數(shù)最少的乘車路線
請輸入第一個站點：白馬公園站
請輸入第二個站點：櫻花路站
白馬公園站 到 櫻花路站 的換乘次數(shù)最少為1 路徑為：
20路：白馬公園站->北京東路九華山站
換乘到11路：北京東路九華山站->櫻花路站
*********************************************************************************
（2）輸入任意兩站點，給出經(jīng)過站點最少的乘車路線
請輸入第一個站點：白馬公園站
請輸入第二個站點：櫻花路站
白馬公園站 到 櫻花路站 的經(jīng)過站點次數(shù)最少為8 路徑為：
20路：白馬公園站->太平門站
換乘到11路：太平門站->板倉街崗子村站
換乘到6路：板倉街崗子村站->板倉村站->板倉街花園路站->櫻駝村站->蔣王廟站->櫻花路站這里我采用的數(shù)據(jù)結(jié)構(gòu)是鄰接表，當(dāng)然也可以使用鄰接矩陣，基本方法是不變的。不過使用鄰接矩陣會浪費大量的空間，運行時也會比鄰接表慢，所以建議使用鄰接表。這道題雖然相對復(fù)雜，但貼近生活實際，對于大家熟悉和應(yīng)用迪杰斯特拉算法有很大的幫助。
以上便是我對這道題的思考，很高興能與大家分享。
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
