type
status
date
slug
summary
tags
category
icon
password
最短路径
最短路
求两点间的最短路径。
（多元最短路）
使用DP思想： 代表经过点K的从I到J的路径长度。
（单源最短路）
无负权，贪心思想。
思路：找到每次更新后值最小的点，然后来维护其指向的点；
链式前向星 存图
建立邻接表；
朴素Dijkstra
由于每次处理完之后还要遍历一遍，找出最小的点，导致时间复杂度为，需要进行优化。
堆优化Dijkstra
使用二叉小根堆，每次堆顶为记录下的最小值的点。
使用中优先队列实现。
桶优Dijkstra
（单源最短路）
思路：将原点入队，更新其指向的点的$dis$值，最后出队，将没入队的终点入队，直到队为空。
使用：
- 判负环
思路：统计入队次数，如果大于$n$则存在负环(一条边权之和为负数的回路)
（判边数）
差分约束
图论建模思想
组元一次不等式，判断是否成立，化为如下形式：
建图，
为防止连通性不成立，加入以下“边”，其对整体判断并无影响：
最后用判断一遍负环便可求证。
全源最短路
Dijkstra 算法不能正确求解带负权边的最短路，因此我们需要对原图上的边进行预处理，确保所有边的边权均非负。
设置一个原点$，从这个点向其他所有点连一条边权为0接下来用 算法求出从 0号点到其他所有点的最短路$h_i$,同时判负环。
假如存在一条从 u 点到 v 点，边权为 w 的边，则我们将该边的边权重新设置为
接下来以每个点为起点，跑 n轮 Dijkstra 算法即可求出任意两点间的最短路了。
分层图
最短路计数
有关Notion安装或者使用上的问题，欢迎您在底部评论区留言，一起交流~
- Author:Grimner
- URL:https://tangly1024.com/article/example-8
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!