Python 最短路径的几种求解方式

目录

• 前言
• 前置知识
• 练习题
• 【单源最短路&迪杰斯特拉】畅通工程（续）
• 【单源最短路 & spfa】最短路径
• 【多源最短路 & 弗洛伊德】牛牛聚会

前言

给出几个点的名称,在给出几个点的路径权重（简称路权）就可以计算一个地图中最短的路权
是不是感觉很神奇。当然啦博主也觉得很神奇，因为博主比较笨嘛,如果只有几个点的图集的话
还可以口算出来图中的最短路,如果有上千个点的话,博主的大脑就不够用了。所以呢咱们掌握最
短路算法还是必须的,至少可以减少我们的脑力劳动嘛。

前置知识

图的话可以大致分为有向图与无向图、图中的边有的是正权值,有的是负权值
有的是两点之间多条路,有的甚至有自环（可以说是灰常的灵活）
创建一个图可以用的数据结构有：
十字链表、邻接多重表、邻接矩阵、边集数组、邻接表
本篇博客前两题解题方法使用的是邻接表,最后一个使用的是邻接矩阵
大家根据自己的喜好进行选择即可,但是思想还是一样的
如果大家对最短路不是很熟的话,推荐大家去看看这个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))

到此这篇关于Python 最短路径的几种求解方式的文章就介绍到这了,更多相关Python 最短路径 内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！