1. 首页
  2. 文章中心
  3. 【学校作业】

【大作业】城市地铁线路最短路规划及路径输出（满分）1）思路分析2）代码实现3）程序分析

57 阅读 0 评论
我是靠谱客的博主 优美大叔，最近开发中收集的这篇文章主要介绍【大作业】城市地铁线路最短路规划及路径输出（满分）1）思路分析2）代码实现3）程序分析，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

4、地铁搭乘方案选择 
轨道交通越来越发达，我们的出行也越来越方便。从学校门口的地铁站乘坐地铁可以到达很多地方。 
 
 
计算地铁出行的最短路径，要求如下：（默认站点与站点之间权值为 1，也可以用时间或距离进行衡量） 
1) 画出从西南石油大学出发，前往世纪城的地铁交通图，分析出哪条线路最短，详细说明分析思路。 
2) 用算法实现你的分析思路，并输出最短路径。（包括代码和运行结果的截图） 
3) 分析算法的性能，至少包括时间复杂度和空间复杂度等。

成都市地铁路线图可以看作是一个有环无向图。
根据老师提供的成都地铁路线图，我一共划分了5条可行路线，并沿途标记了56个站点，相当于无向图中的56个结点。
根据题目要求我将默认站点与站点之间权值为1。

下面是我使用 i p a d ipad ipad 画出的从西南石油大学出发，前往世纪城的地铁交通路线图。

在这里插入图片描述

1）思路分析

对于最短路问题，我这里使用 D i j k s t r a Dijkstra Dijkstra 算法来求得从石油大学站到世纪城站的最短路线并使用prev数组记录最短路径并最后输出所选择路线的站点英文名称。

1. 求得最短路径算法思路分析：

本题实际上可以简化为：

题目背景

由于疫情原因我们没办法开学啦，为了能让同学们不挂科，心善的老师决定布置大作业作为期末成绩的一部分啦

题目描述

一个有环无向图中，有n个结点和m条边，每条边的权值都是1，求得从起点s到终点t的最短路长度，并正序输出最短路径信息。

输入格式

第一行两个正整数，n和m，表示图的结点数和边数。
第二行到n+1行，为n个字符串，代表n个站点信息（中间可能带空格的英文站名） 。
第n+2行到n+2+m行，为三个正整数x，y，z，代表x和y之间连一条权值为z的无向边。

输出格式

首先输出最短路长度：以及最短路径长度。
然后正序输出最短路径上站点的编号和站名信息。

因此可以将各各站点构造n个点，m条边的数据直接使用 D i j k s t r a Dijkstra Dijkstra 算法即可求得最短路。
D i j k s t r a Dijkstra Dijkstra 算法，经典的最短路算法，基于贪心思想的，适用于非负权值图的时间复杂度为 Θ ( n 2 ) Theta(n^2) Θ(n2)优秀算法。

优先队列优化思路：

由于 D i j k s t r a Dijkstra Dijkstra算法 Θ ( n 2 ) Theta(n^2) Θ(n2)的算法瓶颈是每次查找dis数组的最小的值，我们可以使用STL中的优先队列优化这一操作，将 Θ ( n ) Theta(n) Θ(n)的查找优化至 O ( l o g n ) O(logn) O(logn)

但是我作为一名我校优秀的 ACMer 只是使用优先队列怎么行，我决定再进行一些优化（因为优先队列还是太慢啦），考虑如果要优化 D i j k s t r a Dijkstra Dijkstra算法，那么就要摒弃落后的优先队列，由于只需要借用优先队列寻找最小值操作，而优秀的线段树完全可以代替实现。因此我决定补充一个线段树优化版本的 D i j k s t r a Dijkstra Dijkstra。

线段树优化思路：

具体思路如下： D i j k s t r a Dijkstra Dijkstra算法的核心思想就是每次取出最小的 d i s [ i ] , i ϵ [ 1 , n ] dis[i],iepsilon[1,n] dis[i],iϵ[1,n] 且当前的结点i并未被访问过。因此我们使用线段树来全程模拟这个操作。我们用线段树维护区间最小值。每次取出区间 [ 1 , n ] [1,n] [1,n]
中 d i s dis dis最小的点，作为当前节点。根据 D i j k s t r a Dijkstra Dijkstra的设计思想，当前节点的 d i s dis dis已经是最小的了，所以遍历该点能到达的所有子结点，更新子结点的 d i s dis dis,然后由于普通的线段树不支持删除操作（可持久化线段树支持，这里就不展开了）因此直接在线段树中把当前节点位置的值改成 + ∞ +∞ +∞即可(模拟将该点删除)。

二者的理想时间复杂度虽然相同，都是 Θ ( n l o g m ) Theta(nlogm) Θ(nlogm)，但是线段树的常数更小，一般运行起来时间会是优先队列的 1 2 frac{1}{2} 21​！(至于我是怎么得到这个结论的，请看文末)

2. 输出最短路径思路分析：

我这里使用一个 p r e v [ j ] prev[ j ] prev[j]来记录最短路上顶点 j 的前驱，可以在 Θ ( V ) Theta(V) Θ(V)的时间内完成最短路径的恢复（V是边数）。在 d [ j ] d[ j ] d[j]被 d [ j ] = d [ k ] + c o s t [ k ] [ j ] d[ j ] = d[ k ] + cost[ k ][ j ] d[j]=d[k]+cost[k][j]更新时，修改 p r e v [ j ] = k prev[ j ] = k prev[j]=k，这样就可以求出来 p r e v prev prev的数组，可以在以上算法中用路径前驱标记法来还原出来路径。

为了输出站点名称，我使用56个int型整数代表56个沿途可能经过的站点。使用map<int,string>来存储站点信息（英文名）。

2）代码实现

1.数据

本次5条路线一共56个站点（结点）

通过百度百科查找成都市地铁信息梳理得到下面我所需要用到的站点列表：

地铁三号线站点信息
结点1~23

起点：石油大学站 Southwest Petroleum University
钟楼站 Clock Tower
马超西路站 Machao Road West
团结新区站 Tuanjiexinqu
锦水河站 Jinshuihe
三河场站 Sanhechang
金华寺东路站 Jinhua Temple Road East
植物园站 Botanical Garden
一期工程 军区总医院站 Chengdu Junqu General Hospital
熊猫大道站 Panda Avenue
动物园站 Chengdu Zoo
昭觉寺南路站 Zhaojuesi Road South
驷马桥站 Simaqiao
李家沱站 Lijiatuo
前锋路站 Qianfeng Road
红星桥站 Hongxing Bridge
市二医院站 Chengdu Second People’s Hospital
春熙路站 Chunxi Road
新南门站 Xinnanmen
磨子桥站 Moziqiao
省体育馆站 Sichuan Gymnasium
衣冠庙站 Yiguanmiao
高升桥站 Gaoshengqiao

地铁一号线站点信息：
结点：24~31

倪家桥站 Nijiaqiao
桐梓林站 Tongzilin
火车南站 South Railway Station
高新站 Hi-Tech Zone
金融城站 Financial City
孵化园站 Incubation Park
锦城广场站 Jincheng Plaza

终点：世纪城站 Century City

地铁一号线站点信息：
结点：32~37

人民北路站 North Renmin Road
文殊院站 Wenshu Monastery
骡马市站 Luomashi
天府广场站 Tianfu Square
锦江宾馆站 Jinjiang Hotel
华西坝站 Huaxiba

地铁二号线站点信息：
结点：38~39

牛王庙站 Niuwangmiao
东门大桥站 Dongmen Bridge

地铁六号线站点信息：
结点：40~46

顺江路站 Shunjiang Road
三官堂站 Sanguantang
东光站 Dongguang
琉璃场站 Liulichang
琉三路站 Liusan Road
金石路站 Jinshi Road
金融城东站 East Financial City

地铁九号线站点信息：
结点：47

心岛站 Xindao

地铁五号线站点信息：
结点：48~56

西北桥站Xibeiqiao
花牌坊站Huapaifang
抚琴站Fuqin
中医大省医院站Chengdu University of TCM &Sichuan Provincial People’s Hospital
青羊宫站Qingyang Taoist Temple
省骨科医院站Sichuan Provincial Orthopaedic Hospital
科园站Keyuan
九兴大道站Jiuxing Avenue
神仙树站Shenxianshu

梳理完56个结点有了这些信息以后就可以建图了！

然后手动造数据：
一共56个结点与结点信息（站名）和60条无向边

最后整张地铁图的数据及最后的测试数据如下：

输入格式

第一行两个正整数，n和m，表示图的结点数和边数。
第二行到n+1行，为n个字符串，代表n个站点信息（中间可能带空格的英文站名） 。
第n+2行到n+2+m行，为三个正整数x，y，z，代表x和y之间连一条权值为z的无向边。

输出格式

首先输出最短路长度：以及最短路径长度。
然后正序输出最短路径上站点的编号和站名信息。
样例：

56 60
Southwest Petroleum University
Clock Tower	
Machao Road West	
Tuanjiexinqu	
Jinshuihe	
Sanhechang	
Jinhua Temple Road East	
Botanical Garden	
Chengdu Junqu General Hospital	
Panda Avenue	
Chengdu Zoo	
Zhaojuesi Road South	
Simaqiao	
Lijiatuo	
Qianfeng Road	
Hongxing Bridge	
Chengdu Second People's Hospital
Chunxi Road	
Xinnanmen	
Moziqiao	
Sichuan Gymnasium	
Yiguanmiao	
Gaoshengqiao	
Nijiaqiao	
Tongzilin	
South Railway Station	
Hi-Tech Zone		
Financial City	
Incubation Park	
Jincheng Plaza	
Century City
North Renmin Road	
Wenshu Monastery	
Luomashi	
Tianfu Square	
Jinjiang Hotel	
Huaxiba
Niuwangmiao	
Dongmen Bridge	
Shunjiang Road	
Sanguantang	
Dongguang	
Liulichang	
Liusan Road
Jinshi Road	
East Financial City
Xindao
Xibeiqiao	
Huapaifang
Fuqin
Chengdu University of TCM &Sichuan Provincial People’s Hospital
Qingyang Taoist Temple
Sichuan Provincial Orthopaedic Hospital
Keyuan	
Jiuxing Avenue	
Shenxianshu
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
10 11 1
11 12 1
12 13 1
13 14 1
14 15 1
15 16 1
16 17 1
17 18 1
18 19 1
19 20 1
20 21 1
15 32 1
18 35 1
32 33 1
33 34 1
34 35 1
35 36 1
36 37 1
37 21 1
32 48 1
48 49 1
49 50 1
50 51 1
51 52 1
52 53 1
53 23 1
23 22 1
22 21 1
23 54 1
54 55 1
55 56 1
56 26 1
21 24 1
24 25 1
25 26 1
26 27 1
27 28 1
28 29 1
29 30 1
30 31 1
18 39 1
39 38 1
38 40 1
40 41 1
41 42 1
42 43 1
43 44 1
44 45 1
45 46 1
46 47 1
47 29 1

2.优先队列优化版本程序

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<map>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(int i=s;i<=t;++i)
#define lver(i,t,s) for(int i=t;i>=s;--i)
using namespace std;

const int N=1e3+7;
const int INF=1e9+7;
const int mod=2147483647;
const double EPS=1e-6;

struct node
{
    int nex,v,val;
}edge[N<<2];

int n,m;
int head[N],cnt,tot;
bool flag,vis[N];
int dis[N],pre[N],pa[N];
int st,ed;

priority_queue< pair<int,int> >q;
map<int,string>mp;

int read(){
	int x = 0, f = 1, ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
	return x * f;
}

inline void add(int x,int y,int v)
{
    edge[++cnt].nex=head[x];
    edge[cnt].v=y;
    edge[cnt].val=v;
    head[x]=cnt;
}
void dijkstra()
{
    over(i,1,n)dis[i]=INF;
    memset(vis,false,sizeof vis);
    q.push(make_pair(0,st));
    dis[st]=0;
    while(!q.empty())
    {
        int u=q.top().second;
        q.pop();
        if(vis[u])continue;
        vis[u]=true;
        for(int i=head[u];i;i=edge[i].nex)
        {
            int v=edge[i].v;
            if(dis[u]+edge[i].val<dis[v])
            {
                dis[v]=dis[u]+edge[i].val;
                q.push(make_pair(-dis[v],v));
                pre[v]=u;
            }
        }
    }
}
void print()
{
    for(int i=ed;i;i=pre[i])
        pa[++tot]=i;
    cout<<"最短路长度："<<tot<<endl;
    cout<<"最短路径站点编号："<<endl;
    lver(i,tot,2)
    cout<<pa[i]<<" -> ";
    cout<<pa[1]<<endl;
    cout<<"最短路径站点名称："<<endl;
    lver(i,tot,2)
    cout<<mp[pa[i]]<<" -> ";
    cout<<mp[pa[1]]<<endl;
    return;
}
string str;
int main()
{
    st = 1;ed = 31;
    n = read(),m = read();
    for(int i = 1;i <= n;++i){
        getline(cin,str);
        mp[i] = str;
    }
    over(i,1,m){
        int x,y,z;
        x = read(),y = read(),z = read();
        add(x,y,z);add(y,x,z);
    }
    dijkstra();
    print();
    return 0;
}

3.线段树优化版本程序

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<map>
#define over(i,s,t) for(int i=s;i<=t;++i)
#define lver(i,t,s) for(int i=t;i>=s;--i)

using namespace std;
typedef long long ll;
const int N=1e3+7;
const int inf=1e9+7;
const int mod=2147483647;
const double EPS=1e-6;
map<int,string>mp;

int read() {
	int x = 0, f = 1, ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
	return x * f;
}

int n, m,tot;
int st,ed;
int pre[N],pa[N];

struct edge {
	int to, w, nxt;
	edge() {}
	edge(int t, int ww, int nn) {to = t, w = ww, nxt = nn;}
}e[N << 1];

int head[N], k = 0;
void add(int u, int v, int w) {e[k] = edge(v, w, head[u]); head[u] = k++;}

ll ans[N];
struct node {
	ll dis; int x;
	node() {}
	node(ll d, int xx) {dis = d, x = xx;}
}dis[N << 2];

void build(int p, int l, int r) {
	if(l == r) {dis[p].x = l; return;}
	int mid = l + r >> 1;
	build(p << 1, l, mid); build(p << 1 | 1, mid + 1, r);
	dis[p].x = dis[p << 1].x;
}

void change(int p, int l, int r, int x, int y) {
	if(l == r) {dis[p].dis = y; return;}
	int mid = l + r >> 1;
	if(x <= mid) change(p << 1, l, mid, x, y);
	else change(p << 1 | 1, mid + 1, r, x, y);//单点修改的板子操作
	if(dis[p << 1].dis < dis[p << 1 | 1].dis) dis[p] = dis[p << 1];
	else dis[p] = dis[p << 1 | 1];
}

node ask(int p, int l, int r, int ls, int rs) {
	if(ls <= l && r <= rs) {return dis[p];}
	int mid = l + r >> 1; node ans = node(inf, 0), tmp;
	if(ls <= mid) ans = ask(p << 1, l, mid, ls, rs);
	if(rs > mid) {
		node tmp = ask(p << 1 | 1, mid + 1, r, ls, rs);
		if(ans.dis > tmp.dis) ans = tmp;
	}
	return ans;
}

void dijkstra() {
	for(int k = 1; k < n; k++) {
		register int u = ask(1, 1, n, 1, n).x;
		for(int i = head[u]; ~i; i = e[i].nxt) {
			register int v = e[i].to;
			if(ans[u] + e[i].w < ans[v]) {
				ans[v] = ans[u] + e[i].w;
				change(1, 1, n, v, ans[v]);
				pre[v]=u;
			}
		}
		change(1, 1, n, u, inf);
	}
}

void print()
{
    for(int i=ed;i;i=pre[i])
        pa[++tot]=i;
    cout<<"最短路长度："<<tot<<endl;
    cout<<"最短路径站点编号："<<endl;
    lver(i,tot,2)
    cout<<pa[i]<<" -> ";
    cout<<pa[1]<<endl;
    cout<<"最短路径站点名称："<<endl;
    lver(i,tot,2)
    cout<<mp[pa[i]]<<" -> ";
    cout<<mp[pa[1]]<<endl;
    return;
}

string str;
int main() {
    st = 1;ed = 31;
	memset(head, -1, sizeof head);
	n = read(),m = read();
	for(int i = 1;i <= n;++i){
        getline(cin,str);
        mp[i] = str;
    }
	for(int u, v, w, i = 1; i <= m; i++)
        u = read(), v = read(), w = read(), add(u, v, w);
	for(int i = 1; i <= (n << 2); i++)
        dis[i].dis = inf;
	for(int i = 1; i <= n; i++)
        ans[i] = inf;
	//线段树初始化，dis是线段树，ans是答案
	build(1, 1, n);
	change(1, 1, n, st, 0); ans[st] = 0;
	dijkstra();
	print();
	return 0;
}

4.运行结果截图

两种代码的输出相同。因为我写的输出函数一摸一样啦，感兴趣的话您可以亲自运行一下
在这里插入图片描述

3）程序分析

最后到了算法分析的时间了！

算法分析：

时间复杂度

最基础的 d i j k s t r a dijkstra dijkstra算法的时间复杂度为 Θ ( n 2 ) Theta(n^2) Θ(n2)
而经过优化的 d i j k s t r a dijkstra dijkstra算法在核心代码部分，拥有while 循环和 for 循环，while 循环最多循环n 次（n 为顶点个数），for 循环一共循环每个点的边数，也就是总共循环m次。
而for 循环中往优先队列中添加删除数据的复杂度为 Θ ( l o g n ) Theta(log n) Θ(logn)。
线段树修改单点权值的时间复杂度也为 Θ ( l o g n ) Theta(log n) Θ(logn)

综合上述两部分，最终优化后的 D i j k s t r a Dijkstra Dijkstra 算法的时间复杂度是 Θ ( m l o g n ) Theta(mlogn) Θ(mlogn)
而使用普通线段树优化的Dijkstra算法的最差时间复杂度虽然也是 Θ ( m l o g n ) Theta(mlogn) Θ(mlogn)
但是使用线段树的常数会小很多，虽然空间上大了两倍，但是在实际使用的时候时间可以压缩至使用优先队列的 1 2 frac{1}{2} 21​！

当然如果使用zkw线段树进行优化的话时间和空间可以进一步压缩至 1 4 frac{1}{4} 41​，那就是后话了。

空间复杂度

优先队列优化版本额外使用了dis数组和prev数组等等，空间复杂度为 Θ ( k n ) = Θ ( n ) Theta(kn) = Theta(n) Θ(kn)=Θ(n)
线段树优化版本由于线段树的存在要开至少二倍空间，空间复杂度为 Θ ( 2 n + k n ) = Θ ( n ) Theta(2n+kn) = Theta(n) Θ(2n+kn)=Θ(n)

下面给出luoguP4779 【模板】单源最短路径（标准版）三种方法运行的结果(本题中 n n n和 m m m的数据范围达到 1 0 5 10^5 105，下图中的参数分别为运行时间/空间消耗/代码大小/语言)，可以更清晰地看出三者的差别

优先队列优化：

在这里插入图片描述

线段树优化：

在这里插入图片描述

zkw线段树优化：

在这里插入图片描述

以上

最后

以上就是优美大叔为你收集整理的【大作业】城市地铁线路最短路规划及路径输出（满分）1）思路分析2）代码实现3）程序分析的全部内容，希望文章能够帮你解决【大作业】城市地铁线路最短路规划及路径输出（满分）1）思路分析2）代码实现3）程序分析所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(38)

相关文章

python36 +tkinter制作12306火车票查询系统
python36 +tkinter制作12306火车票查询系统
networkx绘制简单图
networkx绘制简单图
李春葆、严蔚敏关于KMP算法的next数组值差1
李春葆、严蔚敏关于KMP算法的next数组值差1
迪杰斯特拉+DFS(应用)
迪杰斯特拉+DFS(应用)
【大作业】城市地铁线路最短路规划及路径输出（满分）1）思路分析2）代码实现3）程序分析
【大作业】城市地铁线路最短路规划及路径输出（满分）1）思路分析2）代码实现3）程序分析
迪杰斯特拉算法c语言6,C语言迪杰斯特拉实现最短路径算法.doc
迪杰斯特拉算法c语言6,C语言迪杰斯特拉实现最短路径算法.doc
西安 地铁线路图
西安 地铁线路图
python无向图最短路径_Dijkstra算法python的实现（有向图/无向图）
python无向图最短路径_Dijkstra算法python的实现（有向图/无向图）

评论列表共有 0 条评论

立即
投稿
返回
顶部