• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

最短路径(dijkstra 与 Floyd)

开发技术 开发技术 4周前 (09-05) 30次浏览
目录
  • 1. 如何建图?
  • 2. Floyd
  • 3. Dijkstra

1. 如何建图?

要跑最短路,首先要有图 ——鲁迅

常用的存储方法有两种,分别是邻接矩阵(用二维数组表示边)和邻接表(模拟链表表示边)两种,他们各有不同的优势和不足:

邻接矩阵 邻接表
使用范围 稠密图 主要是稀疏图
空间耗费 n^2(n节点数) 理论上是 e( e为边条数)
实现方式 二维数组 存储每个节点相连的节点和边权值

通常来讲,在数据范围足够小时,我们采用邻接矩阵,而数据范围大时采用邻接表

邻接矩阵实现:

无权图:

g[x][y]=1 #g[x][y]=1表示x到y有一条边连接
#g[y][x]=1 #去掉注释后是无向图

带权图:

g[x][y]=w #g[x][y]=w表示x到y有一条权值为w的边
#g[y][x]=w #去掉注释后是无向图

2. Floyd

多源最短路算法,用邻接矩阵存储,可以处理负边权,但不能处理负环

多源最短路就是说只要跑一次,任意两点的最短路都能求啦( ̄︶ ̄),而其他单源最短路跑一次只能得出一个点到其他点的最短路

用邻接矩阵存最短路( dis[i][j]表示 ij的最短距离)开一个三重循环(!)

外层枚举中间点,中间枚举起点,内层枚举终点,当三个点互不相同时进行松弛操作,如果经过中间点之后的路程和比原路程短,就更新距离,一轮过后,我们得到了一个新的矩阵,然后我们把中间点换成下一个点,再次松弛,的到一个新的矩阵,执行 n 次之后,第 n个矩阵就是我们的答案啦

#提前将邻接矩阵存在dis数组里,其他不连通的地方初始化成无穷大
for k in range(n): #枚举中间点
    for i in range(n): #枚举起点
        if(i!=k): #节省时间,如果一样就不往下走
            for j in range(n): #枚举终点
                if(i!=j and j!=k): #继续判断,如果有一样的就不往下走
                    dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j])

3. Dijkstra

单源最短路径

将所有节点分成两类:已确定从起点到当前点的最短路长度的节点,以及未确定从起点到当前点的最短路长度的节点(下面简称「未确定节点」和「已确定节点」)。

每次从「未确定节点」中取一个与起点距离最短的点,将它归类为「已确定节点」,并用它「更新」从起点到其他所有「未确定节点」的距离。直到所有点都被归类为「已确定节点」。

用节点 A「更新」节点 B 的意思是,用起点到节点 A 的最短路长度加上从节点 A 到节点 B 的边的长度,去比较起点到节点 B 的最短路长度,如果前者小于后者,就用前者更新后者。这种操作也被叫做「松弛」。

这里暗含的信息是:每次选择「未确定节点」时,起点到它的最短路径的长度可以被确定。

​ ——力扣(LeetCode)

def dijkstra(u):
    #初始化起点 u 到每一个点的距离
    for k in range(n):
        dis[k] = g[u][k]

    print("起点到其他节点的初始距离:",dis)

    used[u] = 1
    for k in range(n):
        minv = float('inf')
        #在未确定节点中找与起点距离最短的
        for i in range(n):
            if not used[i] and dis[i] < minv: 
                minv = dis[i]
                temp = i

        #中转位置, 变为已确定节点,更新距离
        used[temp] = 1 
        for i in range(n):
            if g[temp][i]+dis[temp] < dis[i]:
                dis[i] = g[temp][i]+dis[temp]

        print("第 {} 次迭代,起点到其他节点的距离:{}".format(k,dis))

测试下

with open("path.txt",'r') as f:
    n = int(f.readline())
    weights = f.readlines()

print("顶点数:",n)

dis = [0]*n
used = [0]*n

# 定义邻接矩阵存储图
g = [[0]*n for _ in range(n)]
for u in range(n):
    for v in range(n):
        g[u][v] = int(weights[u].strip().split()[v])

print("邻接矩阵:",g)
# g[u][v] = g[v][u] = w  # 创建图,节点间没有连接赋值为 无穷大

dijkstra(0)

执行结果:

起点到其他节点的初始距离: [65535, 33, 21, 26, 65535, 65535, 65535, 65535]
第 0 次迭代,起点到其他节点的距离:[42, 33, 21, 26, 65535, 42, 65535, 65535]
第 1 次迭代,起点到其他节点的距离:[42, 33, 21, 26, 62, 42, 96, 117]
第 2 次迭代,起点到其他节点的距离:[42, 33, 21, 26, 62, 42, 96, 117]
第 3 次迭代,起点到其他节点的距离:[42, 33, 21, 26, 62, 42, 71, 117]
第 4 次迭代,起点到其他节点的距离:[42, 33, 21, 26, 62, 42, 71, 117]
第 5 次迭代,起点到其他节点的距离:[42, 33, 21, 26, 62, 42, 71, 117]
第 6 次迭代,起点到其他节点的距离:[42, 33, 21, 26, 62, 42, 71, 117]
第 7 次迭代,起点到其他节点的距离:[42, 33, 21, 26, 62, 42, 71, 117]

附上数据

8
65535 33 21 26 65535 65535 65535 65535 65535 
33 0 65535 27 30 65535 65535 65535 65535 
21 65535 0 22 65535 21 65535 65535 65535 
26 27 22 019 36 33 70 91 
65535 30 65535 190 65535 41 64 80 
65535 65535 21 36 65535 0 29 65535 65535 
65535 65535 65535 33 41 290 22 65535 
65535 65535 65535 70 64 65535 22 0 42

references:

https://www.cnblogs.com/Staceyacm/p/10782094.html

https://www.luogu.com.cn/blog/FrozaFerrari/xue-tu-lun-ni-zhen-di-liao-xie-zui-duan-lu-ma-post

https://www.bilibili.com/video/BV1q4411M7r9/?spm_id_from=333.788.videocard.1


喜欢 (0)