👾前言👾
给出几个点的名称,在给出几个点的路径权重（简称路权）就可以计算一个地图中最短的路权
是不是感觉很神奇。当然啦博主也觉得很神奇，因为博主比较笨嘛,如果只有几个点的图集的话
还可以口算出来图中的最短路,如果有上千个点的话,博主的大脑就不够用了。所以呢咱们掌握最
短路算法还是必须的,至少可以减少我们的脑力劳动嘛。
🍁前置知识🍁
图的话可以大致分为有向图与无向图、图中的边有的是正权值,有的是负权值
有的是两点之间多条路,有的甚至有自环（可以说是灰常的灵活）
创建一个图可以用的数据结构有：
十字链表、邻接多重表、邻接矩阵、边集数组、邻接表
本篇博客前两题解题方法使用的是邻接表,最后一个使用的是邻接矩阵
大家根据自己的喜好进行选择即可,但是思想还是一样的
如果大家对最短路不是很熟的话,推荐大家去看看这个UP主的视频,感觉讲的贼好传送门已就绪
十字链表：是有向图存储的一种链式存储结构,可以看成是有向图的邻接表和逆邻接表合起来得到的链表。用十字链表来存储有向图，可以达到高效的存取效果。同时，代码的可读性也会得到提升。
邻接多重表：邻接多重表是无向图的一种存储方式。邻接多重表是邻接表的改进，它把边的两个顶点存放在边表结点中，所有依附于同一个顶点的边串联在同一链表中，由于每条边依附于两个顶点，则每个边表结点同时链接在两个链表中
邻接矩阵：是表示顶点之间相邻关系的矩阵（个人感觉也是最简单的一个,但非常不适合稀疏图）逻辑结构分为两部分：V和E集合，其中，V是顶点，E是边。因此，用一个一维数组存放图中所有顶点数据；用一个二维数组存放顶点间关系（边或弧）的数据，这个二维数组称为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵
边集数组：边集数组（edgeset array）是利用一维数组存储图中所有边的一种图的表示方法。该数组中所含元素的个数要大于等于图中边的条数，每个元素用来存储一条边的起点、终点（对于无向图，可选定边的任一端点为起点或终点）和权（若有的话），各边在数组中的次序可任意安排，也可根据具体要求而定。
知识介绍到此,下面上练习题吧😉
🤺练习题🤺
🌺【单源最短路&迪杰斯特拉】畅通工程（续）🌺
💗问题描述💗
Problem Description
某省自从实行了很多年的畅通工程计划后，终于修建了很多路。不过路多了也不好，每次要从一个城镇到另一个城镇时，
都有许多种道路方案可以选择，而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。
现在，已知起点和终点，请你计算出要从起点到终点，最短需要行走多少距离。
Input
本题目包含多组数据，请处理到文件结束。
每组数据第一行包含两个正整数N和M(0<N<200,0<M<1000)，分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0～N-1编号。
接下来是M行道路信息。每一行有三个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。
再接下一行有两个整数S,T(0<=S,T<N)，分别代表起点和终点。
Output
对于每组数据，请在一行里输出最短需要行走的距离。如果不存在从S到T的路线，就输出-1.
Sample Input
3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2
Sample Output
2
-1
💗问题分析💗
本题目中求解的是单源最短路,经过观察路的边权均是正的,所以我们暂定使用迪杰斯特拉算法
回顾一下迪杰斯特拉算法的模板步骤：
① 设置一个最短距离数组dis（存储某点到任一点的最短距离）
一个父节点数组pre（最短距离访问该节点需要首先访问的那个节点）
一个标记某点是否找到了最短路的列表visit
一个图（可以使用邻接多重表将边初始化进图G）
② 将出发点初始化一下
③ 选出没有被确定最短路的点中，距离源点最近的点
④ 使用他的边集优化边中点的最短距离
⑤ 将该点加入已找到最短路的数组
💗代码实现💗
n,m=map(int,input().split()) visit=[False]*(n+1) dis=[1e8]*(n+1) side=[list(map(int,input().split())) for i in range(m)] G={k:[] for k in range(n)} # s是起点e是终点 s,e=map(int,input().split()) # 初始化邻接表 for i in side: G[i[0]].append([i[1],i[2]]) G[i[1]].append([i[0],i[2]]) dis[s]=0 for _ in range(n): mi=1e8 for i in range(1,len(dis)): if dis[i]<mi and not visit[i]: mi=dis[i] s=i for i in G[s]: if dis[i[0]]>dis[s]+i[1]: dis[i[0]]=dis[s]+i[1] visit[s]=True print(dis[e])
🌺【单源最短路 & spfa】最短路🌺
💗问题描述💗
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。
输入格式
第一行两个整数n, m。
接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。
输出格式
共n-1行，第i行表示1号点到i+1号点的最短路。
样例输入
3 3
1 2 -1
2 3 -1
3 1 2
样例输出
-1
-2
数据规模与约定
对于10%的数据，n = 2，m = 2。
对于30%的数据，n <= 5，m <= 10。
对于100%的数据，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保证从任意顶点都能到达其他所有顶点。
💗问题分析💗
spfa是一种随机方法,有些数据可能会将其卡死。他的思想是使用队列进行算法优化
特点是可以求含有负边权图的最短路。每次将更新过最短长度的点加入队列中（因为该点最短路更新了那么与他相连的点最短路也可能更新）然后从队列中每次取出一个点,对该点所连的点进行边权更新。然后将更新后的点再加入队列中,直到没有点更新为止。
💗代码实现💗
def spfa(n): # 存储修改过最短路权的点 t=[] t.append(n) visit[n]=1 while t: # 每次获取一个更新过路权的点 temp=t.pop() # 更新与他相连点的路权 for i in G[temp]: if dis[i[0]]>dis[temp]+i[1]: dis[i[0]]=dis[temp]+i[1] # 被更新过点所连得点也需要更新,所以将该点加入临时队列 if visit[i[0]]==0: visit[i[0]]=1 t.append(i[0]) n,m=map(int,input().split()) ls=[list(map(int,input().split())) for i in range(m)] G={k:[] for k in range(1,n+1)} for i in ls: G[i[0]].append([i[1],i[2]]) visit=[0]*(n+1) dis=[1e8]*(n+1) dis[1]=0 spfa(1) print(dis)
🌺【多源最短路 & 弗洛伊德】牛牛聚会🌺
💗问题描述💗
给出n个点和m条边，接着是m条边，代表从牛a到牛b需要花费c时间，现在所有牛要到牛x那里去参加聚会，
并且所有牛参加聚会后还要回来，给你牛x，除了牛x之外的牛，他们都有一个参加聚会并且回来的最短时间，
从这些最短时间里找出一个最大值输出
Input
Line 1: Three space-separated integers, respectively: N, M, and X
Lines 2… M+1: Line i+1 describes road i with three space-separated integers:
Ai, Bi, and Ti. The described road runs from farm Ai to farm Bi, requiring Ti time units to traverse.
Output
Line 1: One integer: the maximum of time any one cow must walk.
Examples
Sample Input
4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3
Sample Output
10
💗问题分析💗
不妨先回忆一下怎么使用弗洛伊德算法:
- ① 构造两个图G(用于存储边权) P(用于存储父节点或者说用于存储先驱节点)
- ② 三层循环,判断两点之间最短路是否需要加边
得到的最短路放在G列表中
得到的最短路路径放在P数组中
💗代码实现💗
def F(n): for i in range(1,n+1): for j in range(1,n+1): for k in range(1,n+1): if G[i][j]>G[i][k]+G[k][j]: G[i][j]=G[i][k]+G[k][j] P[i][j]=k n,m,x=map(int,input().split()) G=[[1e7 if i!=j else 0 for i in range(n+1)] for j in range(n+1)] P=[[-1 if i==j else i for i in range(n+1)] for j in range(n+1)] ls=[list(map(int,input().split())) for i in range(m)] for i in ls: G[i[0]][i[1]]=i[2] F(n) for i in G: print(i) for i in P: print(i) ans=[] for i in range(1,n+1): if i==x: continue if G[i][x]!=1e7 and G[x][i]!=1e7: ans.append(G[i][x]+G[x][i]) print(ans) print(max(ans))
