首页 > 其他分享 >最短路

最短路

时间:2024-10-14 11:32:11浏览次数:1  
标签:短路 最小 距离 点集 数值 短距离 dis

dijkstra

更好的理解
主要思想:每次确定一个点的最短距离
我们将图分为2块,一块为最短距离确定的点集,一块为没有确定最短距离的点集,通过前者向后者拓展,来求得答案
我们将所有已经有dis数值的点加入堆,然后每次dis数值最小的它的dis值就是最终的dis距离,所以可以将其加入到距离确定点集中,并用这个点去更新与它直接相连的点的dis值
为什么每次dis数值最小的它的dis值就是最终的dis距离呢?
因为如果其余的dis来更新这个最小距离的话,一定比当前的答案,更劣,因为当前dis已经是最小的了

标签:短路,最小,距离,点集,数值,短距离,dis
From: https://www.cnblogs.com/zcxnb/p/18463736

相关文章

  • 18732 最短路问题
    ###思路1.**建模问题**:将车站和公交线路建模为图,其中车站是节点,公交线路是带权边。2.**选择算法**:使用Dijkstra算法求解从车站1到车站n的最短路径问题。3.**初始化**:创建一个优先队列(最小堆)来存储当前节点和到达该节点的最小花费。初始化所有节点的最小花费为无穷大,起......
  • NOI提高级 图论算法:单源次短路
    DIJ(单源次短路)-TwoPaths-HDU6181DIJ(单源次短路)-TwoPaths-HDU6181-CSDN博客单源次短路(P2829大逃离)单源次短路(P2829大逃离)-CSDN博客单源次短路算法学习笔记单源次短路算法学习笔记-Wiueh_Plus-博客园次短路及次短路计数次短路及次短路......
  • P4779 【模板】单源最短路径(标准版)
    堆优化版:通过定义一个最小堆来实现普通版本中的查找操作点击查看代码#include<iostream>#include<stack>#include<cmath>#include<algorithm>#include<set>#include<vector>#include<climits>#include<string.h>#include<map>#in......
  • 322. 零钱兑换(最短路做法leetcode)
    322.零钱兑换classSolution{publicintcoinChange(int[]coins,intamount){//使用图的方式解决//最短路问题,总金额从0到amount需要走多少步//每一步能迈向的点都是面额里的点+出发点//每步的边权都是1,重要的是走到amount......
  • Leetcode 864. 获取所有钥匙的最短路径
    1.题目基本信息1.1.题目描述给定一个二维网格grid,其中:‘.’代表一个空房间‘#’代表一堵墙‘@’是起点小写字母代表钥匙大写字母代表锁我们从起点开始出发,一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走,也无法穿过一堵墙。如果途经一个......
  • #4. 图的存储、最短路(未完结)
    bro高一才开始自学图论图的存储建议无脑用链式前向星0x01.什么是链式前向星定义(摘自OIwiki)本质上是用链表实现的邻接表具体来说:以有向边的形式,\(head\)数组存当前边的编号,\(e[i].nxt\)数组存上一次加的以\(u\)为起点的边的编号,这样就能实现用\(head[u]\)和\(......
  • 【MATLAB源码-第239期】基于matlab的孔雀优化算法(POA)机器人栅格路径规划,输出做短路
    操作环境:MATLAB2022a1、算法描述孔雀优化算法(PeafowlOptimizationAlgorithm,简称POA)以孔雀(peafowl)的求偶展示行为为灵感,通过模拟这一过程来解决复杂的优化问题。以下是对孔雀优化算法的详细描述:孔雀优化算法是一种基于自然界中孔雀求偶展示行为的群体智能优化算法。孔雀......
  • [Python手撕]网格中的最短路径(可以有k次破墙的机会)
    classSolution:defshortestPath(self,grid:List[List[int]],k:int)->int:n=len(grid)m=len(grid[0])ifm==n==1:return0direction=[[0,1],[-1,0],[1,0],[0,-1]]visited=[[[......
  • Codeforces2014E Rendez-vous de Marian et Robin(分层图最短路)
    题意给定一个无向图,含有\(n\)个点和\(m\)条边。题解点击查看代码#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;constexpri64inf=1e18;voidsolve(){intn,m,h;cin>>n>>m>>h;vector<vector<......
  • 最短路
    最短路及其衍生讲解注意dij堆优化要在\(intu=q.top().seond\)下面写\(if(vis[u])continue;\)和\(vis[u]=1\),因为这是代表\(u\)此时放进与起点同一集合了。判负环spfa做,十分简单,记录一个点入队次数或到某个点路径长度,\(>=n\)即有负环,模板建反图其实就是当我们有多个起点,但......