图 最 短 路
Diikstra朴素
- 非负边权
- 单源最短路
- 顶点数最好小于1000
- 少量数据结构知识和一点点的算法基础
算法描述
这个算法我们采用邻接矩阵来存储，有时候输入数据，并不是我们期待的那样，所以需要对数据做一些处理，也就是把图创建起来的过程。
对于图 G=<V,E>，源点为 s，dist[i] 这个数组表示 s 到i的最短路，visited[i] 表示 dist[i] 是否已经确定(布尔值)，即s到i的最短路是否已经确定。
第三步、初始化
初始化所有顶点的数据如下：dist[i] = 正无穷 (0≤i<n) visited[i] = false(0≤i<n) 那么原点到原点的dist[s] = 0
第四步、找距离最小的点
从所有visited[i]为false的没有被访问过的顶点中找到一个 dist[i] 值最小的，令x=i，并且标记 visited[x] 为 true; 如果找不到，算法结束;
第五步、更新其余点的距离
更新从× 出发的，到达顶点y的最短路dist[y]: dist[y]=min(dist[y], dist[x]+w(x,y))
第六步、重复执行
回到第四步，继续找距离最小值
算法图解
从原点到原点的路径一定是0，那么0的dist就是0
标记完了后我们访问true，更新其余点的距离，那么1 2 3的dist 是1 4 10，接下来找到其中最小的点，是1，那么1就true
继续从1看，只有2联通，且此时距离4>3,2的dist更新为3,第二轮结束;接下来继续找距离最小的点
代码分析
第一步、初始化邻接矩阵
function initEdges(graph, n)
for u -> (0, n-1)
for v -> (0, n-1)
graph[u][v] = inf
第二步、边的添加
function addEdge(graph, u, v, w)
graph[u][v] = min(graph[u][v], w)直接赋值处理不了u到v的情况
第三步、建图
根据题目给出的数据，调用addEdge逐渐完善起来
addEdge(graph, u1, v1, w1)
addEdge(graph, u2, v2, w2)
addEdge(graph, uk, vk, wk)
第四步、框架代码
function Dijkstra(graph, n, s, dist)
visited[]//定义一个dijk数组
DijkstraInit(n, S, visited, dist)
while true
u = DijkstraFindMin(n, visited, dist)//min的值
if u == -1 return
DijkstraUpdate(graph, n, u, visited, dist)//
第五步、Dijkstra 初始化
function DijkstraInit(n, s, visited, dist)
for i -> (0, n-1)
visited[i] = false
dist[i] = inf //无穷大
dist[s] = 0 //为了s出发,到s的距离变成最短路径
第六步、Dijkstra找最小距离
function DijkstraFindMin(n, visited, dist)
u=-1
for i -> (0, n-1)
if visited[i] conintune
if u == -1 or dist[i] < dist[u]
u=i
return u
第七步、Dijkstra 更新
function DijkstraUpdate(graph, n, u, visited, dist)
visited[u] = true //防止找到原点
for i -> (0, n-1)
if visited[i] continue
dist[i] = min(dist[i], dist[u] + graph[u][i]) //所有过程中到s的最短路径,
//和从u过来的最短路径取小者细节剖析
Bellman-Ford
Bellman-Ford算法特点,时间复杂度是O(NM)
- 可求负边权
- 单源最短路
- 顶点数×边数最好小于1000000
- 少量数据结构知识和一点点的算法基础
问题描述
在一个n(n≤500)个顶点和m(m≤2000）条边的连通图上，边有两种类型，种是正常的路；一种是虫洞。正常的路是双向的，行走时花费时间；虫洞是单向的，行走时能让时间倒退。问是否存在某个点出发，并且在过去的某个时间回到该点。
抽象一下: 1、如果没有虫洞，这就是一个无向连通图。也就是说任意两点间可达，那么加入虫洞以后，还是任意两点间可达的。2、只要存在一个负权圈，就可以利用这个负权圈，把时间无限往前推，也就可以实现时光倒流。
问题抽象
求一个任意两点间可达的连通图，是否存在一个负权圈? ---------------------什么是负权圈？比如1---2, 2----3 ,3----1,这么一个圈子 , 使得经过该环的路径权重之和为负值
Bellman-Ford算法可以在最短路存在的情况下求出最短路，并且能够判断图中是否存在负权圈。
算法原理:Bellman-Ford算法是基于这样一个事实：一个图的最短路如果存在，那么最短路中必定不存在负权圈，所以最短路的顶点数除了起点外最多只有n-1 个。Bellman-Ford同样也是利用了最短路的最优子结构性质，用d[j表示起点s到i的最短路，那么边数上限为j的最短路可以通过边数上限为j-1的最短路加入一条边得到，通过n-1次迭代，最后求得s到所有点的最短路。
对于图G=<V,E>，源点为s，d[i] 表示s到i的最短路。
(1)初始化所有顶点d[i]=inf,令d[s]=0，计数器c=0;
(2) 枚举每条边 w(u, v)，如果 d[u] ≠ inf，则更新:d[v] = min(d[v], d[u] + w(u, v) )（这一步叫“松弛”操作)
(3)计数器c自增1，当c==n-1时算法结束，否则继续 重复(2)的步骤;
这个算法并没有考虑到负权圈的问题，如果存在负圈权，那么第（2）步操作的更新会永无止境，所以判定负权圈的算法也就出来了，只需要在第n次继续进行第 (2)步的松弛操作，如果有至少一条边能够被更新，那么必定存在负权圈。
代码分析:
第一步、定义边的数据结构
Edge(u, v, w)
第二步、边的添加
function addEdge(edges, u, v, w)
edges.append( Edge(u, v, w))
第三步、建图
根据题目给出的数据，调用addEdge
addEdge(edges, u1, v1, w1)
addEdge(edges, u2, v2, w2)
addEdge(edges, uk, vk, wk)
第四步、实现松弛操作
function doRelax(edges, d[maxn])
isRelax = False
for i -> (0, edges.size()-1)
u, v, w = edges[i]
if d[u] + w < d[v]
d[v] = d[u] + w
isRelax = True
return isRelax
第五步、算法核心
function bellman(n, s, edges, d[maxn])
for i -> (0, n-1)
d[i] = inf
d[s] = 0
for i -> (1, n-1)
if not doRelax(edges, d)
return false
return doRelax(edges, d)Floyd
- 属于动态规划
- 全源最短路
- 顶点数最好小于100
- 少量数据结构知识和一点点的算法基础
问题描述
对于一个n(n≤ 100)个顶点的有向图（顶点编号是0到n-1），给定一些顶点之间的边 e(u,V, w)，求任意两点之间的最短路。
朴素算法 : 枚举每个点作为起点，求n 次 Dijkstra。时间复杂度就是O(n^3)
第一步、设计状态
令d[k][j][j]为只允许经过结点[0,k)作为中间点的情况下，i到j的最短路。左闭右开,那么左闭右开的节点,那么当k==0的时候,不经过任何节点,,k==1的时候经过0,k==2就是 0 1.依次入场................
第二步、初始状态
d[0][j][j] 代表只经过[0,0]，也就是不经过任何中间点。
第三步、状态转移
令 d[k][j][j] 为只允许经过结点[0,k)作为中间点的情况下，i到j的最短路。
【不包含k】如果最短路不经过k点，则：d[k][i][j] = d[k-1][i][j],实际上就是不经过就是0到k-1的
【包含k】如果最短路经过k点，则： d[k][j][j] = d[k-1][i][k] + d[k-1][k][j]
第四步、状态转移方程
第五步、空间优化
d[j][j] = min(d[i][j], d[i][k] + d[k][j]) (0≤i,j<n,１≤k≤n)
第一步、初始化邻接矩阵
function initEdges(graph, n)
for u -> (0, n-1)
for v -> (0, n-1)
if u ==v
graph[u][v] = 0
else
graph[u][v] = inf
第二步、边的添加
function addEdge(graph, u, v, w)
graph[u][v] = min(graph[u][v], w)
第三步、建图
根据题目给出的数据，调用addEdge
addEdge(graph, u1, v1, w1)
addEdge(graph, u2, v2, w2)
addEdge(graph, uk, vk, wk)
第四步、框架代码
function Floyd(graph, n, s, dist)
for k -> (0, n-1)
for i -> (0, n-1)
for j-> (0, n-1)
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])细节剖析
for k -> (0, n-1) //重中之重,k一定在第一层
for i -> (0, n-1)
for j -> (0, n-1)Dijkstra + Heap
- 非负边权
- 单源最短路
- 顶点数、边数<1000000
- 数据结构前置：邻接表、哈希表、二叉堆
问题描述
给定一张n(n≤10000)个顶点以及m（m≤100000)条边的有向图，顶点编号从0到n-1，该图可以有自环与重边。
求输出0号点到其它所有点的最短路，若不存在此最短路，则最短路的值为-1。
第一步、建图
任何算法我们都要去思考，用什么数据结构来存储，这个算法我们采用邻接表来存储，有时候输入数据，并不是我们期待的那样，所以需要对数据做一些处理，也就是把图创建起来的过程。
第二步、辅助数组
对于图 G=<V,E>，源点为 s，dist[i] 表示 s到i的最短路，visited[i] 表示 dist[i]是否已经确定(布尔值)，即s到i的最短路是否已经确定。
第三步、辅助堆
利用一个小顶堆heap存放二元组(v,dist[v])，小顶堆扮演的是优先队列的作用，dist[v]值越小的，会从优先队列中优先出队。
第四步、初始化
初始化所有顶点的数据如下：
dist[i] =无穷大 (0≤i<n)
visited[i] = false (i<n)
dist[s] = 0
heap.push( (s, dist[s]) ) 不能只插入顶点,距离原点最近,也不能只插入最近距离,因为最近距离无法反馈顶点编号的,我们需要顶点编号
第五步、找距离最小的点
从小顶堆中不断弹出元素u，并且判断visited[u]是否为 true，如果为 true,则继续弹出；否则标记为true，并且从u出发进行"松弛”操作；如果堆为空，算法结束;
第一步、定义距离二元组
Dist(v, w)
第二步、初始化邻接表
function initEdges(n, edges[maxn])
for i -> (0, n-1)
edges[i] = {}
第三步、邻接表加边
function addEdge(edges[maxn], u, v, w)
edges[u].append( Dist(v, w) )
第四步、建图
根据题目给出的数据，调用addEdge
addEdge(edges, u1, v1, w1)
addEdge(edges, u2, v2, w2)
addEdge(edges, uk, vk, wk)
第五步、框架代码
function DijkstraHeap(n, st, edges[maxn], d[maxn])//程序调用大写的,而自己手动调用小写的dijk
heap = Heap()
visited[maxn] = {false}
dijkstraInit(n, st, heap, visited, d)
while( not heap.empty())
u = dijkstraFindMin(heap)
dijkstraUpdate(u,edges,heap,visited,d)
第六步、初始化
function dijkstraInit(n, st, heap, visited[maxn], d[maxn])
for i -> (0, n-1)
d[i] = inf
visited[i] = false
d[st] = 0
heap.push( Dist(st, d[st]))
第七步、获取最小值
function dijkstraFindMin(heap)
s = heap.top()
heap.popO
return s.v
第八步、松弛操作
function dijkstraUpdate(u, edges[maxn], heap, visited[maxn], d[maxn])
if not visited[u]
visited[u] = true
for i -> (0, edges[u].size()-1)
v = edges[u][i].v
w = edges[u][i].w
if( d[u] + w < d[v] )
d[v] = d[u] + w
heap.push( Dist(v, d[v]) )第一点、极大值
inf是一个极大值，也就是必须比可能的最长路的的最大值还要大，也就是：点数n×最大的边权wMax
否则在进行松弛操作的时候，逻辑就错了。就好比线性枚举的时候，求最小值，要先定义一个比所有数据集元素都要大的值一样的道理。
第二点、邻接表存储
之所以用邻接表存储，是因为点数超过1000以后，如果用邻接矩阵存储，内存吃不消，当时时间更吃不消。所以一般如果是用Dijkstra+Heap优化的时候，统一采用邻接表存储。
第三点、堆的作用
对比朴素的利用邻接矩阵存储的Dijkstra，加上堆的作用主要在于，原本需要遍历才能
获取距离dist[u]最小的点u，可以用堆通过O(logn）的时间，快速获取这个最小值对应的）顶点u。
第四点、辅助哈希表
visited[]虽然一般用数组实现，但是实际上是一个哈希表的作用，利用下标的快速插入和查找的特性，能够快速获取一个顶点的最短路是否已经被计算出来。
SPFA
在一个n(n≤10000)个顶点和m(m≤10000）条边的连通图上，边有两种类型，一种是正常的路；一种是虫洞。正常的路是双向的，行走时花费时间；虫洞是单向的，行走时能让时间倒退。问是否存在某个点出发，并且在过去的某个时间回到该点。
这个问题我们在学习Bellman算法的时候见到过，只不过现在n和m的数据范围大了很多，如果还是采用传统的Bellman算法来求解，最坏情况下肯定是会超时的，所以我们引入一种新的算法SPFA（Shortest Path Faster Algorithm）。
算法描述
对于图G=<V,E>，源点为s，d[i]表示s到i的最短路。
(1）利用一个先进先出的队列用来保存待松弛的结点，每次取出队首结点u，并且枚举从u出发的所有边(u,v)，进行松弛操作：
d[v] = min(d[v], d[u] + w(u, v) )
(2)然后判断V点在不在队列中，如果不在就将V点放入队列。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。
第一步、定义边的数据结构
Edge(v, w)
edges0代表以0为起点的邻接表,所有出边的集合;edges1相应的是1出边的集合
第二步、边的添加
function addEdge(edges[maxn], u, v, w)
edges[u].append( Edge(v, w) )
第三步、建图
根据题目给出的数据，调用addEdge
addEdge(edges, u1, v1, w1)
addEdge(edges, u2, v2, w2)
addEdge(edges, uk, vk, wk)
第四步、SPFA框架代码
function SPFA(n, s, edges[maxn], d[maxn], visited[maxn])
q=Queue()
inq ={} //实际上是个hash表,快速查找是不是在队列里
SPFAInit(n, s, d, visited, q, inq) //初始化
while ( not q.empty() )
u = q.front()
q.pop()
inq.remove(u)
if visited[u]++ > n
return true
SPFARelax(u, edges, d, q, inq)
return false
第五步、SPFA初始化
function SPFAInit(n, S, d[maxn], visited[maxn], q, inq)
for i ->(0, n-1)
d[i] = inf
visited[i] = 0
d[s] = 0
visited[s] = 1
q.push(s)
inq.add(s)
第六步、实现松弛操作
function SPFARelax(u; edges[maxn], d[maxn], q, inq)
for i -> (0, edges[u].size()-1)
v, w = edges[u][i]
if d[u] + w < d[v]
d[v] = d[u] + w
if not inq.has(v)
q.push(v)
inq.add(v) 第一点、最短路存在
只要最短路径存在，SPFA算法必定能求出最小值。因为每次将顶点放入队尾，都是经过松弛操作达到的。即每次入队的顶点v对应的最短路径估计值d[v]都在变小。所以算法的执行会使d数组越来越小。
由于我们假定最短路一定存在，即图中没有负权圈，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着d值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。
第二点、最短路不存在
如果存在负权圈，并且起点可以通过一些顶点到达负权圈，那么利用SPFA算法会进入一个死循环，因为d数组的值会越来越小，并且没有下限，使得最短路不存在。
那么我们假设不存在负权圈，则任何最短路上的点必定小于等于n个（没有圈），换言之，用一个数组visited[i]来记录i这个点入队的次数，所有的visited[i]必定都小于等于n，(就是上面有个广搜的时候)所以一旦有一个visited[i]>n，则表明这个图中存在负权圈。
这就是SPFA算法的其中一个终止条件。
第三点、时间复杂度
SPFA算法的最坏时间复杂度为O(nm)，一般的期望时间复杂度为O(km)，k为常数，m为边数（这个时间复杂度只是估计值，具体和图的结构有很大关系，而且很难证明，不过可以肯定的是至少比传统的Bellman-Ford高效很多，所以一般采用SPFA来求解带负权圈的最短路问题）。
题目
Diikstra
网络延迟时间
#define maxn 101
#define edgeType int
#define inf INT_MAX
class Solution {
public:
edgeType graph[maxn][maxn];
void initEdges(int n) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
graph[i][j] = inf;
}
}
}
void addEdge(int u, int v, edgeType w) {
if (graph[u][v] == inf || w < graph[u][v]) {
graph[u][v] = w;
}
}
void dijkstra(int n, int s, edgeType dist[maxn]) {
bool visited[maxn];
for (int i = 0; i < n; ++i) {
visited[i] = false;
dist[i] = inf;
}
dist[s] = 0;
while (1) {
edgeType minDist = inf;
int minIndex;
for (int i = 0; i < n; ++i) {
if (visited[i]) {
continue;
}
if (minDist == inf || dist[i] < minDist) {
minDist = dist[i];
minIndex = i;
}
}
if (minDist == inf) {
break;
}
visited[minIndex] = true;
for (int i = 0; i < n; ++i) {
if (visited[i]) {
continue;
}
int dis = graph[minIndex][i];
if (dis == inf) {
continue;
}
if (dist[i] == inf || dist[minIndex] + dis < dist[i]) {
dist[i] = dist[minIndex] + dis;
}
}
}
}
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
initEdges(n);
for (int i = 0; i < times.size(); ++i) {
int u = times[i][0] - 1;
int v = times[i][1] - 1;
edgeType w = times[i][2];
addEdge(u, v, w);
}
edgeType dist[maxn];
dijkstra(n, k - 1, dist);
int max = 0;
for (int i = 0; i < n; ++i) {
if (dist[i] == inf) {
return -1;
}
if (dist[i] > max) {
max = dist[i];
}
}
return max;
}
};阈值距离内邻居最少的城市
前往目标的最小代价
Bellman-Ford
出差
字母的阶梯游戏
小怂的黄牛f
Floyed
网络延迟时间
到达目的地的方案数
Dijkstra + Heap
Dijkstra求最短路2
蓝桥王国
SPFA
路径
地铁最短路径与最少换乘
保存体力