首页 > 其他分享 >第十一章 图论 Part8

第十一章 图论 Part8

时间:2024-09-12 12:46:05浏览次数:9  
标签:图论 minValVec cur 第十一章 源点 距离 算法 Part8 节点

目录

单源最短路径算法

dijkstra(朴素版)

适用范围(权值不能为负数的单源最短路径)

思路

基本类似Prim算法,只是新加入(确定)点的时候,当前算法算的是距离源点的最短路径,而Prim算法算的是距离最小生成树的最短路径。

minValVec 记录当前每个点到源点的最短路径(随着遍历的过程而更新)
每次并入的步骤:

  1. 确定选哪个节点并入 (不在已访问节点中,距离源点最小的节点) 遍历每个点,得到最小距离的那个点及最小距离。 (顶点编号)
  2. 将第一步选到的点加入到visited中,用一个bool列表记录已经访问的点。
  3. 更新未访问的节点到源点的距离。 (与cur相连的j节点距离源点的距离,比cur加入之前j节点到源点的距离小) =》 因为cur变成访问过的节点后,其他节点需要更新距离这个最新形成的与源点的距离) =》 观察4这个节点随着各个节点的加入,距离源点的最短路径的变化;以及最终作为被选取的点和确认该点最短路径的过程。

如果想记录这个最短路径的边,则使用parent数组(元素值表示使当前节点更新的前一个节点),在第三步更新时记录即可,如果后续节点的加入还会使该点更新,则parent数组实际也会更新。



v,e = map(int,input().split()) # 顶点数,边数
graph = [[float('inf')]* (v+1) for _ in range(v+1)] #邻接矩阵
 
for _ in range(e):
    x,y,k = map(int,input().split())
    #有向图
    graph[x][y] = k
    
 
visited = [False]* (v+1) #是否访问过
minValVec = [float('inf')]* (v+1) #所有点的最小距离列表,初始化每个距离为inf
minValVec[1] = 0 #源点到自己的距离为0
 
for i in range(1,v+1):  # 确认每个点的最短距离
    #1. 确认新加入的点的编号(谁距离源点最近就加谁)
    cur = -1
    minDist = float('inf') #最大的权值 
    for j in range(1,v+1): #遍历所有还未访问点,确认要新加入的点的编号
         
        if not visited[j] and minValVec[j] < minDist:
            minDist = minValVec[j] #更新最小距离,以便在后续迭代中继续比较
            cur = j #更新新加入的点的编号,当循环退出时,确定新加入的点的编号
    if cur == -1: #未找到最小距离的点,说明剩下的点和已经访问的点不连通,退出循环
        break
    #2.记录新加入的点
    visited[cur] = True
    
    #3.因为路径中有了新加入的点,更新每个未确定的点到源点的最小距离
    for j in range(1,v+1):
        if (not visited[j] and graph[cur][j] != float('inf') and minValVec[cur] +  graph[cur][j] < minValVec[j]):#某点到源点的距离可能由于新加入了点而改变
            minValVec[j] = minValVec[cur] +  graph[cur][j]
    
minValVec[v] = -1 if minValVec[v] == float('inf') else minValVec[v]
print(minValVec[v])

算法正确性

那么这个算法为什么就能确定是最短路径呢?实际上按照算法的步骤解释,我们每次选择距离某点的相邻节点时,都是选择最短的(距离源点),假设值为x,而其他的路径非最短,假设值为y1,y2...,那么绕路的话,假设绕路的边的长度为z1,z2...,由于x < y1,y2... 所以x < y1+ z1,y2+z2.(由于算法的适用范围,权值必须非负,所以这里的x,y,z均大于等于0).. ,就更不可能作为最短路径的选取。简单的说,就是每次选距离源点最短的保证了没有其他方式可以使得这个距离更短。
这也是权值必须非负的原因。反例如下:


相当于先走一个长路,然后绕路比直接走反而可以使到源点最短路径更短,所以该算法要求权值非负。

拓扑排序

拓扑排序是经典的图论问题。

先说说 拓扑排序的应用场景。

大学排课,例如 先上A课,才能上B课,上了B课才能上C课,上了A课才能上D课,等等一系列这样的依赖顺序。 问给规划出一条 完整的上课顺序。

拓扑排序在文件处理上也有应用,我们在做项目安装文件包的时候,经常发现 复杂的文件依赖关系, A依赖B,B依赖C,B依赖D,C依赖E 等等。

思路

找到当前入度为0的点(当前入度为0的节点是由zerolist来记录的),加入到结果集,删除它对原图的影响(更新它影响节点的入度,即它的出边连接的点的入度减1),继续这一过程,直到zerolist中没有节点,此时结束,res中记录的即是拓扑排序的过程,表示找完或者没有入度为0的点(有环)。

v,e = map(int,input().split()) # 顶点数,边数
graph = [[float('inf')]* (v+1) for _ in range(v+1)] #邻接矩阵

inDegree = [0] * v #剩余入度(随着选取的进行会更新)
for _ in range(e):
    x,y = map(int,input().split())
    #有向图
    graph[x][y] = 1
    inDegree[y] += 1

from collections import deque
#剩余入度为0的点(用deque是为了删除头部时复杂度o(1)
zeroList = deque()
for i in range(len(inDegree)):
    if inDegree[i] == 0:
        zeroList.append(i)

#拓扑排序的结果放入res
res = []
while(len(zeroList) > 0):
    cur = zeroList.popleft()
    res.append(cur)
    #更新该点影响的点的入度,若修改后入度为0,则加入到zero列表中
    for i in range(v):
        if graph[cur][i] == 1:
            inDegree[i] -= 1
            if inDegree[i] == 0:
                zeroList.append(i)
#print(res) 
if len(res) != v:
    print('-1')
else:
    print(' '.join(map(str,res)))

心得

图的算法中,特别是最近几节的最小生成树,单源最短路径以及拓扑排序,从算法和模拟上是相对可以理解以及模拟出流程(比如手写),但是由于编码上需要一些技巧,编码的逻辑并没有那么容易(包含算法的流程和图的各种输入格式,以及需要引入哪些数据结构来帮助算法的完成),需要熟悉算法流程并多多练习。

标签:图论,minValVec,cur,第十一章,源点,距离,算法,Part8,节点
From: https://www.cnblogs.com/haohaoscnblogs/p/18409954

相关文章

  • 图论
    图论连通性什么是连通?任意两点之间有路径使其相互连接。强连通分量若一张有向图的节点两两互相可达,则称这张图是强连通的强连通分量是一个图的一部分是强联通的,则称这是强连通分量怎么求?这里给出一种方法:tarjanTarjan算法基于对图进行深度优先搜索。我们视每个连通......
  • 【图论】Johnson全源最短路算法
    ·2024-9-11·最后更新时间2024-9-11作者学会了一个叫做\(Johnson\)的算法,所以就有了这篇博客......Johnson算法是一个高效处理全源最短路的算法其实也很慢,但目前是最高效的为了更加方便你们接下来的学习我希望你们已经掌握了基本的最短路算法(SPFA,Dijsktra,Bellman-Ford,Floyd......
  • 第十一章 图论 Part7
    目录最小生成树算法prim算法适用范围:无向图思路kruskal算法适用范围:无向图思路最小生成树算法prim算法适用范围:无向图思路以将所有点归入最小生成树为目标,每次并入一个,最终生成最小生成树。每次并入的步骤:确定选哪个节点并入(不在最小生成树里的,距离最小生成树(已并入的......
  • 代码随想录day 56 || 图论6
    Prim算法应用场景是主要是找到一个无向连通图的最小生成树,即连接所有节点且权重总和最小的树//prim三部曲//1,找到距离当前最小树最近节点//2,节点入树//3,更新mindist//更新树funcupdateMinDist(edges[][]int,nodeint){ for_,edge:=rangeedges{ ifed......
  • 代码随想录day55 || 图论5
    并查集197图中是否存在有效路径varfather[]intfuncvalidPath(nint,edges[][]int,sourceint,destinationint)bool{ //使用并查集算法,涉及到的操作,包括init,find,issample,join father=make([]int,n) fori,_:=rangefather{//init father[i]=i }......
  • 代码随想录训练营 Day53打卡 图论part04 110. 字符串接龙 105. 有向图的完全可达性 10
    代码随想录训练营Day53打卡图论part04一、卡码110.字符串接龙本题与力扣127题是一样的,所以这里使用力扣127题。字典wordList中从单词beginWord到endWord的转换序列是一个按下述规格形成的序列beginWord->s1->s2->…->sk:    每一对相邻的单词只......
  • 图论篇--代码随想录算法训练营第五十三天打卡| 110. 字符串接龙,105.有向图的完全可达
    110.字符串接龙题目链接:110.字符串接龙题目描述:字典strList中从字符串beginStr和endStr的转换序列是一个按下述规格形成的序列: 序列中第一个字符串是beginStr。序列中最后一个字符串是endStr。 每次转换只能改变一个字符。 转换过程中的中间字符串必须是字典......
  • 计算机三级 - 数据库技术 - 第十一章 故障管理 笔记
    第十一章故障管理内容提要:了解故障管理类型及数据库恢复技术了解数据转储技术了解如何利用日志文件进行数据恢复了解硬件容错方案11.1故障管理概述故障类型及解决方案:事务内部故障:导致数据不一致预期的事务内部故障:可通过事务过程本身发现解决办......
  • 第十一章 图论 Part4
    目录任务127.单词接龙思路Kama105.有向图的完全可达性思路463.岛屿的周长思路任务127.单词接龙字典wordList中从单词beginWord到endWord的转换序列是一个按下述规格形成的序列beginWord->s1->s2->...->sk:每一对相邻的单词只差一个字母。对于1<=i<=......
  • 图论板子
    Primtypedefpair<int,int>P;intprim(){intans=0,cnt=0;priority_queue<P,vector<P>,greater<P>>q;fill(d+1,d+n+1,INF);d[1]=0;q.push(P(d[1],1));while(!q.empty()&&cnt<......