Dijkstra算法与北京地铁路径规划

一.Dikjstra算法：

（部分内容出自博客Dijkstra算法（迪杰斯特拉算法）_持之以恒2016-CSDN博客）

基本思想：

Dikjstra算法采用广度优先策略，从起始点v0开始，层层向外拓展。正是如此，导致其搜索成功率较高但是 时间复杂度 较大为O(n²)。

将顶点划分为两种：集合S：已经确定最短路径的顶点；集合U：没有确定最短路径的顶点。

操作步骤

1.初始：从s开始，S中只有元素S，其他元素都在U中。且U中顶点与s的距离定义为：若U，s直接连接，则其距离就为其邻接矩阵定义的距离。若U，s不直接连接，则其距离为无穷大（INF）。这样定义是因为可以优先考虑与D相邻的顶点，实现BFS。

2.从U中选出距离最小的顶点k，并把k加入到S中。且k的前序就是v0。

3.更新距离：以k为依托，与k直接连接的顶点到v0的距离（但不一定最小）就等于其到k的距离加上k到v0的距离。若这个距离小于当前记录的距离，则这个顶点的前序就是k。

4.重复2，3到遍历结束。

图解示例

----- S是已计算出最短路径的顶点的集合
----- U是未计算出最短路径的顶点的集合
----- C(3)表示顶点C到起点D的最短距离为3

选择顶点D
S={D(0)}
U={A(∞), B(∞), C(3), E(4), F(∞), G(∞)}

选取顶点C
S={D(0), C(3)}
U={A(∞), B(13), E(4), F(9), G(∞)}

选取顶点E
S={D(0), C(3), E(4)}
U={A(∞), B(13), F(6), G(12)}

选取顶点F
S={D(0), C(3), E(4), F(6)}
U={A(22), B(13), G(12)}

选取顶点G
S={D(0), C(3), E(4), F(6), G(12)}
U={A(22), B(13)}

选取顶点B
S={D(0), C(3), E(4), F(6), G(12), B(13)}
U={A(22)}

选取顶点A
S={D(0), C(3), E(4), F(6), G(12), B(13), A(22)}
U={}

代码如下：

void Dijkstra(int v0){

int minweight,minv;

int wfound[MAXVEX]={0};

for(int i=0;i<vnum;i++){

sweight[i]=mat[v0][i].weight;

spath[i]=v0;

wfound[i]=0;

}

sweight[v0]=0;

wfound[v0]=1;

for(int i=0;i<vnum-1;i++){

minweight =INF;

for(int j=0;j<vnum;j++){

if(!wfound[j]&&sweight[j]<minweight){

minv = j;

minweight = sweight[minv];

}

}

wfound[minv]=1;

for(int j=0;j<vnum;j++){

if(!wfound[j]&&(minweight + mat[minv][j].weight)<sweight[j]){

sweight[j]=minweight+mat[minv][j].weight;

spath[j]=minv;

}

}

}

}

cpp

二.北京地铁

题面如下：

编写一个程序实现北京地铁最短乘坐（站）线路查询，输入为起始站名和目的站名，输出为从起始站到目的站的最短乘坐站换乘线路。注：1. 要求采用Dijkstra算法实现；2）如果两站间存在多条最短路径，找出其中的一条就行。

【输入形式】

文件bgstations.txt为数据文件（可从课程网站中课程信息处下载），包含了北京地铁的线路及车站信息。其格式如下：

<地铁线路总条数>

<线路1> <线路1站数>

<站名1> <换乘状态>

<站名2> <换乘状态>

...

<线路2> <线路2站数>

<站名1> <换乘状态>

<站名2> <换乘状态>

...

说明：文件第一行为地铁总线路数；第二行第一个数为某条地铁线线号（如，1为1号线），第二个数为该条地铁线的总站数（如1号线共有23站），两数之间由一个空格分隔；第三行两个数据分别为地铁站名及换乘状态（0为非换乘站，1为换乘站），两数据间由一个空格分隔；以下同，依次为该线地铁其它站信息。在一条线路信息之后是下条地铁线路信息，格式相同。若某条地铁线为环线，则首站与末站信息相同（如北京地铁2号线，首站信息“西直门 1” ，末站信息为“西直门 1”）。例如本题提供的bgstations.txt文件（可从课程网站中课程信息处下载）内容如下：

13

1 23

苹果园 0

古城 0

八角游乐园 0

八宝山 0

玉泉路 0

五棵松 0

万寿路 0

公主坟 1

军事博物馆 1

木樨地 0

南礼士路 0

复兴门 1

西单 1

...

2 19

西直门 1

积水潭 0

鼓楼大街 1

...

西直门 1

...

该文件表明当前北京地铁共有13条线路（不含郊区线路），接着为每条线路信息。

打开当前目录下文件bgstations.txt，读入地铁线路信息，并从标准输入中读入起始站和目的站名（均为字符串，各占一行）。

【输出形式】

输出从起始站到目的站的乘坐信息，要求乘坐站数最少。换乘信息格式如下：

SSN-n1(m1)-S1-n2(m2)-...-ESN

其中：SSN和ESN分别为起始站名和目的站名；n为乘坐的地铁线路号，m为乘坐站数。
【样例输入】

西土城

北京西站

【样例输出】

西土城-10(1)-知春路-13(2)-西直门-4(2)-国家图书馆-9(4)-北京西站

（或西土城-10(1)-知春路-13(2)-西直门-2(1)-车公庄-6(2)-白石桥南-9(3)-北京西站）

【样例说明】

打开文件bgstations.txt，读入地铁线路信息，并从标准输入中读入查询起始站名为“西土城”，目的站名为“北京西站”。程序运行结果两站间最少乘坐站数的乘坐方式为“西土城站乘坐10号线1站至知春路站换乘13号线乘坐2站至西直门站换乘4号线乘坐2站至国家图书馆站换乘9号线乘坐4站至北京西站”。本样例存在两条最少站数的乘坐方式，只要找出一条就可以。

【评分标准】

对于同一个起始站和目的站，如果存在多条最少站数的乘坐方式，只要找出其中一条就可以。测试点全通过得满分。

本题求解分为三个方面：建立图，用Dijkstra算法求出最短路径的前驱集合，用前驱集合输出符合要求的路径。

建立图：

注意，本题的站点是分地铁线给出的，也就是说，换乘站会出现在多条路线中。这也是建图的时候需要注意，并通过此建立线路间联系的。

由于本题没有给出边 信息 ，所以构建边的原则就是：前一个站点和现在的站点必须要用边连接起来：这样的算法是可以解决环路的。要实现这种方法，就需要使用两个变量来存储当前和上一个结点序号。

具体操作如下：

用v1记录上一个站点，开始时v1为-1。v2记录当前输入的站点。

读入v2，若不是换乘站，就将其与直接加入到顶点集中，然后与v1（如果不是-1的话）连接起来。

若v2是换乘站，则其有可能已经被加入到了顶点集中。这时候就要去搜索其是不是在顶点集中，如果使得的话，v2就是这个顶点的下标。如果不是的话，就和上面一个加入到顶点集中。然后和上一个站连接。

代码如下：

int add_vex(Vex p){

if(!p.istransfer){

v[vnum++]=p;

return vnum-1;

}

else{

for(int i=0;i<vnum;i++){

if(!strcmp(p.station_name,v[i].station_name))

return i;

}

v[vnum++]=p;

return vnum-1;

}

}

void create_graph(){

FILE *src = fopen("bgstations.txt","r");

int v1,v2;

int line_cnt;

Vex tmp_vex;

fscanf(src,"%d",&line_cnt);

for(int i=0;i<line_cnt;i++){

int lineID,staion_cnt;

fscanf(src,"%d%d",&lineID,&staion_cnt);

v1 = v2 = -1;

for(int j=0;j<staion_cnt;j++){

fscanf(src,"%s%d",tmp_vex.station_name,&tmp_vex.istransfer);

v2 = add_vex(tmp_vex);

if(v1 !=-1){

mat[v1][v2].weight=mat[v2][v1].weight =1;

mat[v1][v2].line=mat[v2][v1].line =lineID;

}

v1 = v2;

}

}

fclose(src);

}

cpp

用Dijkstra算法求出最短路径前驱path：

方法和代码已经给出，不再重复。

用path求路径：

注意path[i]是i的前驱，所以要求v1到v2的路径我们只能倒过来从v2开始找。找到的下标存在final_path这个数组里面。但是注意这个路径是倒过来找的，所以我们需要把这个数组在逆置一下，变成顺着的路径。

对于输出部分：

由于我们只输出换乘站（和高德差不多），所以我们需要记录当前在哪条线上面，以及在这条线上走过了多少站。到路线发生变化的时候再输出换乘站。代码如下

int tmp = index_e;

while(tmp!=index_b){

final_path[path_cnt++]=tmp;

tmp = spath[tmp];

}

final_path[path_cnt++]=tmp;

reverse();

put_path();

void reverse(){

int temple[MAXVEX]={0};

for(int i=0;i<path_cnt;i++){

temple[path_cnt-1-i]=final_path[i];

}

for(int i=0;i<path_cnt;i++){

final_path[i]=temple[i];

}

}

void put_path(){

int now,last,way_now,len;

last =0,now =1;

way_now = mat[final_path[last]][final_path[now]].line;

len = 0;

printf("%s",v[final_path[0]].station_name);

for(;now<path_cnt;now++){

if(way_now!=mat[final_path[last]][final_path[now]].line){

printf("-%d(%d)-%s",way_now,len,v[final_path[last]].station_name);

way_now = mat[final_path[last]][final_path[now]].line;

len = 0;

}

len++;

last = now;

}

printf("-%d(%d)-%s",way_now,len,v[final_path[last]].station_name);

}

cpp

最后附上完整代码：

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MAXVEX 1000

#define INF 32767

typedef struct station

{

char station_name[32];

int istransfer;

} Vex;

typedef struct edge

{

int weight;

int line;

} Edge;

Vex v[MAXVEX];

int vnum = 0;

Edge mat[MAXVEX][MAXVEX];

int add_vex(Vex p)

{

if (!p.istransfer)

{

v[vnum++] = p;

return vnum - 1;

}

else

{

for (int i = 0; i < vnum; i++)

{

if (!strcmp(p.station_name, v[i].station_name))

return i;

}

v[vnum++] = p;

return vnum - 1;

}

}

void create_graph()

{

FILE *src = fopen("bgstations.txt", "r");

int v1, v2;

int line_cnt;

Vex tmp_vex;

fscanf(src, "%d", &line_cnt);

for (int i = 0; i < line_cnt; i++)

{

int lineID, staion_cnt;

fscanf(src, "%d%d", &lineID, &staion_cnt);

v1 = v2 = -1;

for (int j = 0; j < staion_cnt; j++)

{

fscanf(src, "%s%d", tmp_vex.station_name, &tmp_vex.istransfer);

v2 = add_vex(tmp_vex);

if (v1 != -1)

{

mat[v1][v2].weight = mat[v2][v1].weight = 1;

mat[v1][v2].line = mat[v2][v1].line = lineID;

}

v1 = v2;

}

}

fclose(src);

}

int visited_dfs[MAXVEX] = {0};

void DFS(int i)

{

printf("%sn", v[i].station_name);

visited_dfs[i] = 1;

for (int j = 0; j < vnum; j++)

{

if (mat[i][j].weight > 0 && visited_dfs[j] == 0)

{

DFS(j);

}

}

}

int sweight[MAXVEX];

int spath[MAXVEX];

void Dijkstra(int v0)

{

int minweight, minv;

int wfound[MAXVEX] = {0};

for (int i = 0; i < vnum; i++)

{

sweight[i] = mat[v0][i].weight;

spath[i] = v0;

wfound[i] = 0;

}

sweight[v0] = 0;

wfound[v0] = 1;

for (int i = 0; i < vnum - 1; i++)

{

minweight = INF;

for (int j = 0; j < vnum; j++)

{

if (!wfound[j] && sweight[j] < minweight)

{

minv = j;

minweight = sweight[minv];

}

}

wfound[minv] = 1;

for (int j = 0; j < vnum; j++)

{

if (!wfound[j] && (minweight + mat[minv][j].weight) < sweight[j])

{

sweight[j] = minweight + mat[minv][j].weight;

spath[j] = minv;

}

}

}

}

int final_path[MAXVEX] = {0};

int path_cnt = 0;

void reverse()

{

int temple[MAXVEX] = {0};

for (int i = 0; i < path_cnt; i++)

{

temple[path_cnt - 1 - i] = final_path[i];

}

for (int i = 0; i < path_cnt; i++)

{

final_path[i] = temple[i];

}

}

void put_path()

{

int now, last, way_now, len;

last = 0, now = 1;

way_now = mat[final_path[last]][final_path[now]].line;

len = 0;

printf("%s", v[final_path[0]].station_name);

for (; now < path_cnt; now++)

{

if (way_now != mat[final_path[last]][final_path[now]].line)

{

printf("-%d(%d)-%s", way_now, len, v[final_path[last]].station_name);

way_now = mat[final_path[last]][final_path[now]].line;

len = 0;

}

len++;

last = now;

}

printf("-%d(%d)-%s", way_now, len, v[final_path[last]].station_name);

}

int main()

{

for (int i = 0; i < MAXVEX; i++)

{

for (int j = 0; j < MAXVEX; j++)

{

mat[i][j].weight = INF;

mat[i][j].line = 0;

}

}

create_graph();

char begin[32], end[32];

scanf("%s%s", begin, end);

int index_b, index_e;

for (int i = 0; i < vnum; i++)

{

if (!strcmp(begin, v[i].station_name))

{

index_b = i;

}

if (!strcmp(end, v[i].station_name))

{

index_e = i;

}

}

Dijkstra(index_b);

int tmp = index_e;

while (tmp != index_b)

{

final_path[path_cnt++] = tmp;

tmp = spath[tmp];

}

final_path[path_cnt++] = tmp;

reverse();

put_path();

}

cpp

相关知识

Dijkstra算法与北京地铁路径规划
【物流配送中的最短路径算法】：优化配送，降低成本
路径规划算法：基于花授粉优化的路径规划算法
采摘机械臂路径规划算法研究现状综述
物流配送路径优化方法有哪些
物流配送路径规划模型及其改进TLBO算法研究
基于机器视觉的草坪修剪机器人自主路径规划算法研究
葡萄园植保机器人路径规划算法
解码配送距离：Java编程中的物流里程挑战与解决方案
基于正余双弦自适应灰狼优化算法的医药物流配送路径规划

网址: Dijkstra算法与北京地铁路径规划 https://www.huajiangbk.com/newsview2590423.html