首页 > 其他分享 >图- 最短路径

图- 最短路径

时间:2023-11-16 18:13:18浏览次数:35  
标签:结点 源点 ++ 短路 路径 最短 算法

图的最短路径

最小生成树与最短路径

最小生成树

  • 包含图中的所有点。
  • 能保证整个树中的所有路径之和最小

最短路径

  • 不一定包含图中的所有结点。(有向图,部分结点无法以最短路方式被加入)
  • 能保证从一点到图中其他点的路径最小

Dijkstra迪杰斯特拉算法

Dijkstra按路径长度递增的次序产生最短路径,最终得到的是从图中某个顶点到所有其他(存在最短路)的顶点的最短路径

算法步骤

  1. 把图中所有顶点分为两组:已求出最短路的和未求出最短路的,前者初始时只包含源点v0;
  2. 按与源点的最短路长度依次递增的顺序,逐个把未求出最短路的集合中的顶点加入已求出最短路的结点,同时每加入一个新结点,都要对其他结点的最短路长度进行更新。
  3. 最终所有结点都被加入已求出最短路的结点。

辅助数据结构

  1. 一维数组S[i]
    用于标记结点是否已经被求出了最短路径。
  2. 一维数组Path[i]
    记录每个结点的直接前驱结点的编号。
  3. 一维数组D[i]
    记录从源点到每个结点的当前最短路长度。
    如果加入新结点后,发现某些结点以新加入的结点作为中转结点会使其到源点的最短路径比当前已求出的最短路径更小,则需要对其进行更新。更新后再选择D中值最小的结点,重复上述步骤。

算法实现

void ShortestPath_DIJ(AMGraph G, int v0) {
    n = G.vexnum;
    for(v = 0; v < n; v++) {
        S[v] = false; D[v] = G.arcs[v0][v];
        Path[v] = (D[v] < MaxInt) ? v0 : -1; // 不与源点直接相连的 最短路长度初始化为-1
    }
    S[v0] = true; D[v0] = 0; // 加入源点 下面是主循环
    for(i = 1; i < n; i++) {
        min = MaxInt;
        for(w = 0; w < n; w++)
            if(!S[w] && D[w] < min) {v = w; min = D[w];}
        S[v] = true;
        for(w = 0; w < n; w++) {
            if(!S[w] && (D[v] + G.arcs[v][w] < D[w])) 
	// 加入新结点后 对之前求出的其它结点最短路径长度进行更新
                D[w] = D[v] + G.arcs[v][w], Path[w] = v;
        }
    }
}

算法分析

时间复杂度为O(n²)。
即使是只想知道从源点到某个特定结点的最短路,也需要完整执行一次Dijkstra算法。

Floyd弗洛伊德算法

Floyd算法用求每一对结点之间的最短路径,也可以调用n次Dijkstra算法解决,但Floyd更优雅。两者时间复杂度都是O(n³)
就是遍图中的所有结点,每次都把遍历到的当前结点作为中转结点进行插入(就是考察如果加上这个新结点,现有的所有最短路径长度会不会更新)。

算法步骤

  1. 在两顶点间插入一个中转结点(也就是给二维数组赋值),通过比较两种方式的路径长度,得到两顶点间的最短路径长;
  2. 不断重复上述步骤,每插入一个新结点,就更新一次所有的最短路径值。

辅助数据结构

  1. 二维数组D[i][j]:记录两顶点间最短路长度。
  2. 二维数组Path[i][j]:记录两顶点间的中转结点,便于中间过程进行比较更新。

算法实现

void ShortestPath_Floyd(AMGraph G) {
    for(i = 0; i < G.vexnum; i++)  // 初始化
        for(j = 0; j < G.vexnum; j++) {
            D[i][j] = G.arcs[i][j];
            Path[i][j] = (D[i][j] < MaxInt && i != j) ? i : -1;
        }
    for(k = 0; k < G.vexnum; k++) 
        for(i = 0; i < G.vexnum; i++) 
            for(j = 0; j < G.vexnum; j++) 
                if(D[i][k] + D[k][j] < D[i][j]) { 
		// 通过比较两顶点间的 当前最短路径长度 与 经过中转结点的最短路径长度 
		// 得到更小的一个作为新的最短路径长度
                    D[i][j] = D[i][k] + D[k][j];
                    Path[i][j] = Path[k][j];
                }
}

标签:结点,源点,++,短路,路径,最短,算法
From: https://www.cnblogs.com/iszxh/p/17836395.html

相关文章

  • shell脚本定义变量和文件路径拼接
    在shell脚本定义变量为xx="xxx"例如把一个路径或文件名定义为一个变量inputPath="/mnt/RNASeq/Result"fileName="202308071824_210901003_2D230327074US2S2745DX"在路径"/mnt/RNASeq/Result"下面有多个文件夹,例如:L01、L02、···每个文件夹下存在多个fa文件,例如“2023080......
  • excel公式 提取文件路径
    =SUBSTITUTE(LEFT(@CELL("filename",A1),FIND("[",@CELL("filename",A1))-1),"[","")=SUBSTITUTE(LEFT(@CELL("filename",A1),FIND("[",@CELL("filename",A1))-1),"[","&quo......
  • Python 获取指定目录所有深层文件路径(包括子目录下的所有文件)
    importosdefget_all_deep_files_in_folder(folder_path):all_files=[]file_paths=os.listdir(folder_path)foriteminfile_paths:fp=os.path.join(folder_path,item)ifos.path.isfile(fp):all_files.append(fp)......
  • macos:查看文件的完整路径(12.7)
    一,第一种方法:打开终端,把文件拖动到终端,即可以看到完整的路径:二,第二种方法:用快捷键复制路径:打开窗口后同时按下:option+command+c然后在可输入的软件中粘贴即可:说明:刘宏缔的架构森林—专注it技术的博客,网站:https://blog.imgtouch.com原文: https://blog.imgtouch.......
  • 【路径规划】基于动态窗口法DWA算法的机器人动态避障路径规划研究附Matlab代码
    ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,代码获取、论文复现及科研仿真合作可私信。......
  • 最短路径树
    \(md\)怎么今天写一个题就遇到一个没学过的知识点?我真的什么都没学过吗???最短路径树是一棵树,满足\(dis(u,root)\)等于在原图中源点到\(u\)的最短路长度。求这个很简单,也是直接\(dij\)就行了。但是又要求这棵树边权和最小,于是有了一个贪心算法,即时地更新\(pre\)。感觉不......
  • 《全网最细-深度解析 Istio Ambient Mesh 流量路径》摘要
    ----NodeA首次上行--------APREROUTING-jztunnel-PREROUTING-Aztunnel-PREROUTING-ptcp-mset--match-setztunnel-pods-ipssrc-jMARK--set-xmark0x100/0x100-Aztunnel-PREROUTING-mmark--mark0x100/0x100-jACCEPTfromallfwmark0x100/0x100lookup101101......
  • 最短路树
    定义最短路树:以图上一个点为根节点,删去部分边后所形成的树,树的边权满足任意一点与根结点的路径长度等于图上两点的最短路径长度。求法可以采用dij求解。每次更新\(dis_v\)时,记录每个点最后一次用来更新的边,即为最短路树。核心代码如下,时间复杂度为dij的时间复杂度即\(......
  • 图论——最短路 学习笔记
    图论——最短路学习笔记其实是复习性质的,主要是总结,证明什么的,等上大学再说。定义单源最短路:从一个点\(q\)出发,到其他所有点的最短路。全源最短路:任意两点见最短路。算法对比算法FloydJohnsonBellman–FordSPFADijkstra类型全源全源单源单源单源......
  • CATIA——CATIA日志文件路径在哪里?CATIA点击出现黑框闪退,CATIA日志文件在哪里?CATIA启
    背景:CATIA点击出现黑框闪退,CATIA日志文件在哪里?CATIA启动失败,也没有报错,是什么原因?百度之后,说的检查显卡驱动程序、重新安装CATIA、缺少acadres.dll等方法,感觉都不适用。于是看到一条说是让检查CATIA日志,感觉可行。1、CATIA日志文件路径在哪里?(1)C:\Users\zhaojj01\AppData\Loca......