图 最 短 路

Diikstra朴素

1. 非负边权
2. 单源最短路
3. 顶点数最好小于1000
4. 少量数据结构知识和一点点的算法基础

算法描述

这个算法我们采用邻接矩阵来存储，有时候输入数据，并不是我们期待的那样，所以需要对数据做一些处理，也就是把图创建起来的过程。

对于图 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 trueu = 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] = falsedist[i] = inf //无穷大dist[s] = 0 //为了s出发,到s的距离变成最短路径
第六步、Dijkstra找最小距离
function DijkstraFindMin(n, visited, dist)u=-1for i -> (0, n-1)if visited[i] conintuneif u == -1 or dist[i] < dist[u]u=ireturn u
第七步、Dijkstra 更新
function DijkstraUpdate(graph, n, u, visited, dist)visited[u] = true //防止找到原点for i -> (0, n-1)if visited[i] continuedist[i] = min(dist[i], dist[u] + graph[u][i]) //所有过程中到s的最短路径,//和从u过来的最短路径取小者

细节剖析

Bellman-Ford

Bellman-Ford算法特点,时间复杂度是O(NM)

1. 可求负边权
2. 单源最短路
3. 顶点数×边数最好小于1000000
4. 少量数据结构知识和一点点的算法基础

问题描述
在一个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 = Falsefor i -> (0, edges.size()-1)u, v, w = edges[i]if d[u] + w < d[v]d[v] = d[u] + wisRelax = Truereturn isRelax
第五步、算法核心
function bellman(n, s, edges, d[maxn])for i -> (0, n-1)d[i] = infd[s] = 0for i -> (1, n-1)if not doRelax(edges, d)return falsereturn doRelax(edges, d)

Floyd

1. 属于动态规划
2. 全源最短路
3. 顶点数最好小于100
4. 少量数据结构知识和一点点的算法基础

 问题描述
对于一个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 ==vgraph[u][v] = 0elsegraph[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

1. 非负边权
2. 单源最短路
3. 顶点数、边数<1000000
4. 数据结构前置：邻接表、哈希表、二叉堆

 问题描述
给定一张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])//程序调用大写的,而自己手动调用小写的dijkheap = 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] = infvisited[i] = falsed[st] = 0heap.push( Dist(st, d[st]))第七步、获取最小值
function dijkstraFindMin(heap)s = heap.top()heap.popOreturn s.v
第八步、松弛操作
function dijkstraUpdate(u, edges[maxn], heap, visited[maxn], d[maxn])if not visited[u]visited[u] = truefor i -> (0, edges[u].size()-1)v = edges[u][i].vw = edges[u][i].wif( 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]++ > nreturn trueSPFARelax(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] = infvisited[i] = 0d[s] = 0visited[s] = 1q.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] + wif 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

路径

地铁最短路径与最少换乘

保存体力