开发网站监控平台,安装wordpress只有文字,山东营销网站建设联系方式,网站建站分为两种文章目录 前言一、单源最短路径1、单源最短路径问题2、Dijkstra 初始化a、参数b、初始化参数c、算法步骤 3、Dijkstra 算法详细步骤a、第一轮算法执行b、第二轮算法执行c、第三轮算法执行d、第四轮算法执行e、第五轮算法执行f、第六轮算法执行 4、java算法实现 二、多源最短路径… 文章目录 前言一、单源最短路径1、单源最短路径问题2、Dijkstra 初始化a、参数b、初始化参数c、算法步骤 3、Dijkstra 算法详细步骤a、第一轮算法执行b、第二轮算法执行c、第三轮算法执行d、第四轮算法执行e、第五轮算法执行f、第六轮算法执行 4、java算法实现 二、多源最短路径1、多源最短路径问题2、Floyd初始化a、参数b、参数初始化c、算法步骤 3、Floyd算法详细步骤4、java 算法实现 前言
最短路径的算法有两个Dijkstra算法 和 Floyd算法。Dijkstra算法 解决的是 单源 最短路径问题。Floyd算法解决的是 多源 最短路径问题并且可以处理负权图。今天要讲的就是Dijkstra算法。加feng--Insist(大写的i)进java交流群讨论互联网技术。可索要PPT等资料。其他资料建议先看本篇博客。Dijkstra算法和Floyd算法https://blog.csdn.net/weixin_43872728/article/details/100662957代码位置https://github.com/fengfanli/dataStructuresAndAlgorithm/tree/master/src/com/feng/algorithm/self_learn
一、单源最短路径
1、单源最短路径问题
解决的问题: 求解单源最短路径,即各个节点到达源点的最短路径或权值。如下图中 考察其他所有节点到源点的最短路径和长度局限性: 无法解决权值为负数的情况资料 可先看匹配视频https://www.bilibili.com/video/BV1o44y1B7NM/代码待上传。
2、Dijkstra 初始化
首先已知的是 给定 邻接矩阵表示的图Graph、源点S、终点T。
a、参数
参数:
参数名解释S记录当前已经处理过的源点到最短节点U记录还未处理的节点dist[]记录各个节点到起始节点的最短权值path[]记录各个节点的上一级节点(用来联系该节点到起始节点的路径)
b、初始化参数
顶点集S: 节点A到自已的最短路径长度为0。只包含源点即S{A}代码中没有这个这里是为了步骤清晰而设置的。顶点集U: 包含除A外的其他顶点. 即U{B,C,D,E,F,G}dist[]: 源点还不能到达的节点,其权值为∞
名ABCDEFGdist[]:0123456初始化值:0466∞∞∞
path[]: 记录当前节点的前驱节点下标(源点还不能到达的节点为-1)
名ABCDEFGpath[]:0123456初始化值:0000-1-1-1
c、算法步骤 初始化设定除源节点以外的其它所有节点到源节点的距离为INFINITE(一个很大的数)且这些节点都没被处理过。如上图所示从源节点出发更新相邻节点(图中为B、C、D)到源节点的距离。然后在所有节点中选择一个最段距离的点作为当前节点。标记当前节点为done(表示已经被处理过)与步骤2类似更新其相邻节点的距离。(这些相邻节点的距离更新也叫 松弛目的是让它们与源节点的距离最小。因为你是在当前最小距离的基础上进行更新的由于当前节点到源节点的距离已经是最小的了那么如果这些节点之前得到的距离比这个距离大的话我们就更新它)。步骤3做完以后设置这个当前节点已被done然后寻找下一个具有最小代价(cost)的点作为新的当前节点重复步骤3.如果最后检测到目标节点时其周围所有的节点都已被处理那么目标节点与源节点的距离就是最小距离了。如果想看这个最小距离所经过的路径可以回溯前提是你在步骤3里面加入了当前节点的最优路径前驱节点信息。
我总结了下可用如下几句话代替 两步走 从dist[]中在集合U中的选择最小距离加入到S中作为当前节点。(最小距离就是 当前节点到源点的最小距离)遍历当前节点的邻边节点更新dist[]和path[] 如果经过当前节点邻边权重 邻边节点则改变dist[]和path[]否者不改变。
3、Dijkstra 算法详细步骤
a、第一轮算法执行 如上图因为dist[]中排出掉集合U中节点最小值是4也就是节点B所以将B纳入到集合S中圈中。 首先 在dist[]数组中并在集合U中 最小值是节点B既当前节点其邻边有C和E所以看是否要更新C和E。 节点C因为C的最小距离dist[1](B的最小距离)41(B到C的距离)5 dist[2](C的最小距离) 6所以 dist[2]5path[2]1节点E因为E的最小距离 dist[1](B的最小距离)47(B到E的距离)11 dist[4] (E的最小距离)无穷大所以 dist[4]11,path[4]1 第一轮算法两个邻边节点C、E有改变
b、第二轮算法执行 如上图因为dist[]中排出掉集合U中节点最小值是5也就是节点C所以将C纳入到集合S中圈中。首先在dist[]数组中并在集合U中 最小值是节点C既当前节点其邻边有E和F所以看是否要更新E和F。 节点E因为C的最小距离 dist[2](也就是C的最小距离)56(C到E的距离)11 dist[4](E的最小距离) 11所以不动节点F因为F的最小距离 dist[2](也就是C的最小距离)54(C到F的距离)9 dist[5] (F的最小距离)无穷大所以 dist[5]9,path[5]2 第二轮算法两个邻边节点仅有 F有改变
c、第三轮算法执行 如上图因为dist[]中排出掉集合U中节点最小值是6也就是节点D所以将D纳入到集合S中圈中。首先在dist[]数组中并在集合U中 最小值是节点D既当前节点其邻边有C和F所以看是否要更新C和F。节点C因为C的最小距离 dist[3](也就是D的最小距离)62(D到C的距离)8 dist[2](C的最小距离) 5 所以不动节点F因为F的最小距离 dist[3](也就是D的最小距离)65(D到F的距离)11 dist[5] (F的最小距离)9所以不动第三轮算法两个邻边节点C、F都没有改变
d、第四轮算法执行 如上图因为dist[]中排出掉集合U中节点最小值是9也就是节点F所以将F纳入到集合S中圈中。首先在dist[]数组中并在集合U中 最小值是节点F既当前节点其邻边有E和G所以看是否要更新E和G 。节点E因为E的最小距离 dist[5](也就是F的最小距离) 9 1(F到E的距离)10 dist[4](E的最小距离) 11所以 dist[4] 10,path[4]5节点G因为G的最小距离 dist[5](也就是F的最小距离) 9 8(F到G的距离)17 dist[6](G的最小距离) 无穷大所以 dist[6]17,path[6]5第四轮算法两个邻边节点E、G都有改变
e、第五轮算法执行 如上图因为dist[]中排出掉集合U中节点最小值是9也就是节点F所以将F纳入到集合S中圈中。首先在dist[]数组中并在集合U中 最小值是节点E既当前节点其邻边有G所以看是否要更新G 。节点G因为G的最小距离 dist[4](也就是E的最小距离) 10 6(E到G的距离)16 dist[6](G的最小距离) 17所以 dist[6]16,path[6]4第五轮算法邻边 节点G有改变
f、第六轮算法执行 如上图因为dist[]中排出掉集合U中节点最小值是16也就是节点G所以将G纳入到集合S中圈中。首先在dist[]数组中并在集合U中 最小值是节点G既当前节点其没有邻边。第六轮算法邻边节点G没有改变到此算法遍历结束
4、java算法实现
给定矩阵表示的Graph结构。输入源点v0和终点v1。 二、多源最短路径
1、多源最短路径问题
上面的Dijkstra 解决的是单源最短路径的问题首先要给定 开始节点和终止结点如果换了开始和终止节点那就要每次都要重新跑一次。那就引出了多源最短路径问题就是执行一次算法求出每两个点之间的最短距离这就是多源最短路径算法。这个算法代码略简单一些。思想只有一个要算两个点之间的最短距离就看有没有第三个点使得
2、Floyd初始化
首先已知的是 给定 **邻接矩阵表示的图Graph。
a、参数
参数名解释A[][]函数中的参数需要返回存储的是节点的前置节点。path[][]存储的是每两点之间的所需距离。
b、参数初始化
参数名解释A[][]就是图的赋值从代码中可以看出比较简单path[][]默认都是-1.表示从A点到B点是直达的。
c、算法步骤
对于每个顶点v体现在代码的第一层for循环和任意一顶点i,j(体现代码的第二、三层循环),切 i!j、v!i、v!j。如果A[i][j] A[i][v] A[]v[j]则将A[i][j] 更新为 A[i][v] A[v][j] 的值并且将path[i][j]改为v。
3、Floyd算法详细步骤
4、java 算法实现
package com.feng.algorithm.self_learn.floyd.floyd1;/*** 学习视频https://www.bilibili.com/video/BV1LE411R7CS*/
public class FloydAlgorithm {public static void main(String[] args) {int[][] graph new int[4][4];int N Short.MAX_VALUE;graph[0] new int[]{0, 5, N, 7};graph[1] new int[]{N, 0, 4, 2};graph[2] new int[]{3, 3, 0, 2};graph[3] new int[]{N, N, 1, 0};int[][] path new int[4][4];int[][] A Floyd.floyd(graph, path);int u 1;int v 0;Floyd.printPath(u, v, path);System.out.println();System.out.println(u - v shortest path is : A[u][v]);}
}
class Floyd {/*** 佛洛依德算法给定邻接矩阵表示的图* path[][]:存放路径中间的节点如果是-1就是直达* A[][]:存放任意两个节点之间的距离* 举例从1-0从A得出距离是6从path得出 1-3-2-0* param graph* param path*/static int[][] floyd(int[][] graph, int[][] path) {int n graph.length;int v, i, j;int[][] A new int[n][n];for (i 0; i n; i) {for (j 0; j n; j) {A[i][j] graph[i][j];path[i][j] -1;}}for (v 0; v n; v) {for (i 0; i n; i) {for (j 0; j n; j) {if (A[i][j] A[i][v] A[v][j]) {A[i][j] A[i][v] A[v][j];path[i][j] v;}}}}return A;}/*** 递归打印路径* param u* param v* param path*/static void printPath(int u, int v, int[][] path) {if (path[u][v] -1) { // 如果等于 -1 。说明就是直达的System.out.printf(u - v );} else {int mid path[u][v];printPath(u, mid, path);printPath(mid, v, path);}}
}
