首页 > 其他分享 >最短路总结

最短路总结

时间:2023-05-24 20:57:02浏览次数:65  
标签:总结 www cnblogs 短路 Dijkstra html https com

单源最短路

Bellman-Ford SPFA Dijkstra H-Dijkstra
思路 遍历全边,直到不变 宽搜渐进,入队再更 找最近点,更新邻点,找完不再用 取负入队,大根堆找点,其余相同
负边权
判负环
时间复杂度 O(nm) O(km~nm) O(m+n^2) O(mlogn)
适用于 为什么不用SPFA 稀疏图 还是优化吧 非负边权
链接 https://www.cnblogs.com/V-sama/p/17422894.html https://www.cnblogs.com/V-sama/p/17426721.html https://www.cnblogs.com/V-sama/p/17426750.html https://www.cnblogs.com/V-sama/p/17426844.html

基本上是H-Dijkstra>Dijkstra>SPFA>Bell-Ford

多源最短路

Floyed H-Dijkstra Johnson
思路 动规三重循环 n次Dijkstra 虚拟结点,映射非负,H-Dijkstra
负边权
判负环
时间复杂度 O(n^3) O(nmlogn) O(nm+nmlogn)
适用于 稠密图 非负边权 稀疏图
链接 https://www.cnblogs.com/V-sama/p/17429313.html https://www.cnblogs.com/V-sama/p/17426844.html https://www.cnblogs.com/V-sama/p/17429389.html

标签:总结,www,cnblogs,短路,Dijkstra,html,https,com
From: https://www.cnblogs.com/V-sama/p/17429454.html

相关文章

  • 5.24每日总结
    <%@pagecontentType="text/html;charset=UTF-8"language="java"%><html><head><title>添加用户</title><style>body{background-color:#f2f2f2;font-family:Aria......
  • Johnson 全源最短路
    全源最短路,换一种说法就是n个单源最短路,可以用n次Bellman-Ford或SPFA,非负边权还可以用Dijkstra,可是有负边权用前两个算法还是慢,如果我们能把负边权映射成非负边权的话,一切就都好办了这里我们引入一个虚拟结点,它和所有点的初始距离都是0,然后,我们求出来这个结点和其他店的最短路h,然......
  • SQL高级语法学习总结(二)
    SQL高级语法学习总结(一)。现在我们接着说sql的高级用法。SQLCREATEDATABASE语法CREATEDATABASEdbname;CREATEDATABASE语句用于创建数据库。 SQLCREATETABLE语法CREATETABLEtable_name(column_name1data_type(size),column_name2data_type(size),column_name3dat......
  • SQL高级语法学习总结(一)
    基础语法呢,就是简单的对行列进行增删改。SQL基础语法学习总结,高级用法无非是条件更多,能实现的需求更多,其中涉及到非常多的关键字,本篇博客就进行一下总结。本文所有用法均在mysql环境下测试通过。其他数据库可能某些关键字会有不同。SQLSELECTLIMIT子句 SELECTLIMIT子句用于规......
  • 软件工程 期末个人总结
    (1)本学期对第一周提出的计划完成情况。1.基本达到了老师的要求,能够完成老师交给的一个mis系统,完成最基本的增删改查,并把所有的功能都进行流程化。(学生选课管理系统)2.能够实现安卓的开发实现手机端的一个地铁查询系统。(双人团队项目)3.在团队项目中担任队长督促队员完成团队项目,并......
  • Floyed 全源最短路
    全源最短路,顾名思义,就是任意两点之间的最短路floyed的思路就是每次选一个点k,如果k不在u和v路径上,就不改变,如果k在u和v的路径上,进行松弛操作d[u][v]=min(d[u][v],d[u][k]+d[k][v])例题洛谷B3647【模板】Floyd算法#include<iostream>#defineforup(i,l,r)for(inti=l;i<=r;......
  • 软件工程课程个人总结
    1.关于第一周的计划对于增删改查相对来说比较熟悉,对于测试不那么慌张,从我自身感受来说,无论是上学期的期末还是这学期的开学考试,我整个人都是一个比较慌的状态,就像是高中考数学,明明会做但是因为自己的紧张到处出错,看着一点一点流逝的时间只能更加紧张,但是现在感觉没那么慌张了,或许......
  • 团队问题总结
    经过本团队成员讨论本次团队主要的三个问题第一个:项目需求分析不到位第二个:团队会议效率过低第三个:团队分工出现重复现象本周开展了团队会议,重点讨论团队任务收尾工作,同时总结出现的问题。对于本次团队收尾工作,较为顺利,主要第一阶段已完成项目的整体,新的内容就是在原有的基......
  • 课程个人总结
    在这一学期中,开始提出了目标要求:本学期目标 对于这个目标基本完成,对于AndroidStudio项目有所了解,在项目中完成了Android手机端项目的构建。对于项目来说,了解到项目对我们并非太远,项目也是基于数据库的构建,此外关于条件的限制、界面的美化也是构建项目的基本方法。在对于Androi......
  • Trace32下对ARM内存访问Access Classes总结
    原内容来源于T32帮助文档debugger_arm.pdf的ARMSpecificImplementations->AccessClasses,这里记录方便查询。首先介绍AccessClasses都有哪些选项,然后介绍常见的AccessClasses组合,最后介绍如何创建合法的AccessClasses组合。1.单个AccessClasses描述2.常见AccessCla......