【图论学习】邻接矩阵/邻接表，Floyed / Djikstra / SPFA 算法求最短路径

图论学习 小结

4月学习 - 图论
跟着三叶姐学算法啦

学习建图的两种类型：邻接矩阵 和 邻接表 (链式向前星)
学习图论最短路径的三个算法：Floyd - Dijkstra - SPFA

例题

本章以力扣 743. 网络延迟时间 为例

约定 N 为点数，M 为边数

一、邻接矩阵

这是一种使用二维矩阵来进行存图的方式。

适用于边数较多的「稠密图」使用，当边数量接近点的数量的平方，即 m ≈ n 时，可定义为「稠密图」。

个人不建议使用，容易爆内存

建图

邻接矩阵数组：graph [节点数][节点数] ，N可根据实际情况定

	int[][] graph = new int[N][N];

添加数据

添加数据 - ori源节点 glo目标节点 val权重

	void add(int ori, int glo, int val) {graph [ori][glo] = val;}

二、邻接表 - 链式向前星

这是一种以链式结构存储图的方式，与数组存储单链表的实现一致（头插法）

适用于边数较少的「稀疏图」使用，当边数量接近点的数量，即 m ≈ n 时，可定义为「稀疏图」。

建图

headAll 数组：存储是某个节点所对应的边的集合（链表）的头结点；
集合存的是 以目标节点为源点，可以访问哪些边，这里是最后遍历到的边的下标
由于是链式存储，所以这里存储的也可以理解为头节点

	static int headAll[] = new int[N];

curPoint 数组：
当前这条边(下标为idx)访问的目标节点（有向图）

	static int curPoint[] = new int[M];

nextSide 数组：用于是以链表的形式进行存边，该数组就是用于找到下一条边；
这里存的是 下一条以a为源点出发的边 的 idx

	static int nextSide[] = new int[M];

value 数组：用于记录参数边数组中，下标为idx的有向边的 权重/值

	static int value[] = new int[M];

idx 是用来对边进行编号的，遍历给的边数组、边集合

	static int idx = 0;

因此当我们想要遍历所有由 a 点发出的边时，可以使用如下方式：
i != -1 因为初始化链表头Arrays.fill(headAll,-1);
也就是访问第一条由a为源节点的边时，将next = null类似的操作 变成了 next = -1
也可以理解为初始化链表尾hh

	for (int i = headAll[a]; i != -1; i = nextSide[i]) {int b = curPoint[i], c = value[i]; // 存在由 a 指向 b 的边，权重为 c}

首先 idx 是用来对边进行编号的，也可以理解为为了遍历给予的参数 {边数组、边集合}

	static int idx = 0;

添加数据 - 链表存值

a 源节点ori b 目标节点gol c权重/值val

    static void add(int a, int b, int c) {curPoint[idx] = b;nextSide[idx] = headAll[a];headAll[a] = idx;value[idx] = c;idx++;}

逐行理解

遍历参数数组中，数组第idx个值，其中的被指向节点赋值给curPoint[idx]

	curPoint[idx] = b;

作为链表，需要把当前节点和a源节点连的其他边连接起来
所以把目前a的头节点，作为 当前节点的next ， 再把当前节点作为a的头节点
类似代码 cur.next = head;

	nextSide[idx] = headAll[a];

把当前节点的index 放到 a为源节点链表的头节点 ; 代码 head = cur;

	headAll[a] = idx;

位置的权重赋值

	value[idx] = c;

index自增，因为要遍历参数集合的下一个数据
类似代码 : for(int i=0;i<m; i++ ) 中的 i++

	idx++;

三、邻接矩阵 - Floyd算法

注释直接写在代码中了。
时间复杂度为O(n^3)，因此不建议使用此算法

class Solution {static int INF = 0x3f3f3f3f;static int[][] times = new int[1][1];static int n = 0 , k = 0;static int grath[][] = new int[1][1];// 邻接矩阵 + floydpublic int networkDelayTime(int[][] times, int n, int k) {this.times = times;this.n = n;this.k = k;grath = new int[n][n];//初始化for(int i=0;i<n;i++){for(int j=0;j<n;j++){grath[i][j] = grath[j][i] =  i==j ? 0 : INF;}}//存图for(int[] t:times){int u = t[0] , v = t[1] , w = t[2];grath[u-1][v-1] = w;}floyd();int ans = -1;for(int i=0;i<n;i++){ans = Math.max(ans,grath[0][i]);}return ans > INF / 2 ? -1 : ans;}public static void floyd(){//遍历中间节点for(int p=0;p<n;p++){//遍历起始节点for(int i=0;i<n;i++){//遍历目标节点for(int j=0;j<n;j++){//更新最短路径grath[i][j] = Math.min(grath[i][j],grath[i][p]+grath[p][j]);}}}}
}

四、邻接矩阵 - Djikstra 算法

class Solution {static int INF = 0x3f3f3f3f;static int[][] times = new int[1][1];static int n = 0 , k = 0;static int grath[][] = new int[1][1];public int networkDelayTime11(int[][] times, int n, int k) {this.times = times;this.n = n;this.k = k;grath = new int[n][n];//初始化for(int i=0;i<n;i++)for(int j=0;j<n;j++)grath[i][j] = grath[j][i] =  i==j ? 0 : INF;//存图for(int[] t:times){int u = t[0] , v = t[1] , w = t[2];grath[u-1][v-1] = w;}dijkstra();int ans = -1;for(int i=0;i<n;i++)ans = Math.max(ans,dist[i]);return ans > INF / 2 ? -1 : ans;}static int dist[] = new int[1];static boolean vis[] = new boolean[1];public static void dijkstra(){dist = new int[n];vis = new boolean[n];//初始化Arrays.fill(dist,INF);Arrays.fill(vis,false);//只有起点最短距离为0dist[k-1] = 0;//迭代所有点的长度for(int p=0;p<n;p++){// 每次找到「最短距离最小」且「未被更新」的点 tint t = -1;for(int i=0;i<n;i++){if(vis[i]==true) continue;if(t==-1 || dist[i]<dist[t] ) t = i;}// 标记点 t 为已更新vis[t] = true;// 用点 t 的「最小距离」更新其他点for(int i=0;i<n;i++){dist[i] = Math.min(dist[i],dist[t] + grath[t][i]);}}}
}

五、邻接表 - Djikstra 算法

class Solution {static int INF = 0x3f3f3f3f;static int[][] times = new int[1][1];static int n = 0 , k = 0;static int dist[] = new int[1];static boolean vis[] = new boolean[1];static int headAll[] = new int[1];static int curPoint[] = new int[1];static int nextSide[] = new int[1];static int value[] = new int[1];static int idx = 0;static void add(int a, int b, int c) {curPoint[idx] = b;nextSide[idx] = headAll[a];headAll[a] = idx;value[idx] = c;idx++;}// 链式向前星 + dijkstrapublic int networkDelayTime(int[][] times, int n, int k) {this.times = times;this.n = n;this.k = k;this.headAll = new int[n];this.curPoint = new int[times.length];this.nextSide = new int[times.length];this.value = new int[times.length];this.idx = 0;// 初始化链表头Arrays.fill(headAll,-1);//存图for(int[] t:times){int u = t[0]-1 , v = t[1]-1 , w = t[2];add(u,v,w);}//最短路dijkstra();int ans = -1;for(int i=0;i<n;i++){ans = Math.max(ans,dist[i]);}return ans > INF / 2 ? -1 : ans;}//链式dijkstra写法public static void dijkstra(){dist = new int[n];vis = new boolean[n];Arrays.fill(vis, false);Arrays.fill(dist, INF);dist[k-1] = 0;//使用优先队列存储 { 当前点，距离源点最短路径 }PriorityQueue<int[]> queue = new PriorityQueue<>((a,b)->{return a[1]-b[1];});queue.add(new int[]{k-1,0});while(!queue.isEmpty()){int point[] = queue.poll();int id = point[0],step = point[1];if(vis[id]) continue;vis[id] = true;//使用该点更新其他点的「最短距离」for(int i = headAll[id];i!=-1;i=nextSide[i]){//被指向的节点int element = curPoint[i];//如果数值更大，就将它变成更小值if(dist[element] > dist[id] + value[i]){//这段一定要记住：//因为是从ori指向gol// 所以 [最短距] = 从ori点到源点的最短距 + [ori-gol]当前这条边的长度dist[element] = dist[id] + value[i];queue.add(new int[]{element,dist[element]});}}}}}

六、邻接表 - SPFA 算法 (存在负边权)

适用范围：当给定的图存在负权边 且 不存在负权回路时，适合使用SPFA算法。
（负权回路可额外判定）

动态逼近法：通过双端队列存储待更新的节点，每次取出队首节点（暂称之为cur节点）。通过cur更新 所有cur可连接节点（称为next节点） 的最短路径，如果next节点的最短路径被更新，且next节点不存在当前队列中，就将next入队。不断更新最短路径直到没有最短路径可更新为止，此时队列为空，退出循环，结束操作。

class Solution {static int INF = 0x3f3f3f3f;static int[][] times = new int[1][1];static int n = 0 , k = 0;static int dist[] = new int[1];static boolean vis[] = new boolean[1];static int headAll[] = new int[1];static int curPoint[] = new int[1];static int nextSide[] = new int[1];static int value[] = new int[1];static int idx = 0;static void add(int a, int b, int c) {curPoint[idx] = b;nextSide[idx] = headAll[a];headAll[a] = idx;value[idx] = c;idx++;}// 链式向前星 + spfapublic int networkDelayTime(int[][] times, int n, int k) {this.times = times;this.n = n;this.k = k;this.headAll = new int[n];this.curPoint = new int[times.length];this.nextSide = new int[times.length];this.value = new int[times.length];this.idx = 0;// 初始化链表头Arrays.fill(headAll,-1);//存图for(int[] t:times){int u = t[0]-1 , v = t[1]-1 , w = t[2];add(u,v,w);}spfa();int ans = -1;for(int i=0;i<n;i++){ans = Math.max(ans,dist[i]);}return ans > INF / 2 ? -1 : ans;}//链式 spfa写法//主要用应用于有负边权的情况（如果没有负边权，推荐使用Dijkstra算法）。//利用了邻接表建图，数据结构的基础一定要掌握好，而且该算法很容易超时，被卡，必须要谨慎选择该算法。public static void spfa(){dist = new int[n];vis = new boolean[n];// 起始先将所有的点标记为「未入队」和「距离为正无穷」Arrays.fill(dist,INF);Arrays.fill(vis,false);dist[k-1] = 0;// 使用「双端队列」存储，存储的是点编号Deque<Integer> deque = new ArrayDeque<>();deque.addLast(k-1);vis[k-1] = true;while(!deque.isEmpty()){// 每次从「双端队列」中取出，并标记「未入队」int point = deque.pollFirst();vis[point] = false;// 尝试使用该点，更新其他点的最短距离// 如果更新的点，本身「未入队」则加入队列中，并标记「已入队」for(int i=headAll[point]; i!=-1;i=nextSide[i]){int element = curPoint[i];//有更小的值，当前的element被更新了if(dist[element] > dist[point] + value[i]){dist[element] = dist[point] + value[i];//如果已在队列，就不加入队列，等待它自动判断更新就行if(vis[element]) continue;//不在队列，就将此节点加入队列（因为最短值已经更新了）deque.addLast(element);vis[element] = true;}}}}

以下文献转载自：http://blog.csdn.net/morgan_xww/article/details/6279596

/*
SPFA(Shortest Path Faster Algorithm) [图的存储方式为邻接表]
是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。
算法大致流程是用一个队列来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素，
并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。 直到队列为空时算法结束。
它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径，可以处理负边。
SPFA 在形式上和BFS非常类似，不同的是BFS中一个点出了队列就不可能重新进入队列，但是SPFA中
一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本
身被改进，于是再次用来改进其它的点，这样反复迭代下去。
判断有无负环：如果某个点进入队列的次数超过V次则存在负环（SPFA无法处理带负环的图）。
SPFA算法有两个优化算法 SLF 和 LLL：
SLF：Small Label First 策略，设要加入的节点是j，队首元素为i，若dist(j)<dist(i)，则将j插入队首，
否则插入队尾。
LLL：Large Label Last 策略，设队首元素为i，队列中所有dist值的平均值为x，若dist(i)>x则将i插入
到队尾，查找下一元素，直到找到某一i使得dist(i)<=x，则将i出对进行松弛操作。
引用网上资料，SLF 可使速度提高 15 ~ 20%；SLF + LLL 可提高约 50%。
在实际的应用中SPFA的算法时间效率不是很稳定，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法。
*/ 

疑难点

在写代码的时候对这些代码存有疑惑

下面两种写法哪一种更好呢？ 答案是第二种
原因： 「并不是一定不会更新」 具体移步：链接

return ans==INF ? -1 : ans;return ans > INF / 2 ? -1 : ans;

总结

以上就是今天要讲的内容，本文仅仅简单介绍了图论中的建图以及三种基础的最短路径算法，如有错误感谢指出，如有疑问感谢留言。