写点什么

单源最短路问题

作者:秋名山码民
  • 2022 年 5 月 11 日
  • 本文字数:1450 字

    阅读完需:约 5 分钟

单源最短路问题

单源最短路问题(又称为 SSSP 问题),给定一张有向图,n 个点,m 个边,节点以[1,n]之间的连续整数编号,(x,y,z)描述一条从 x 出发,到达 y,长度为 z 的有向边。设 1 号点为起点,求长度为 n 的数组 dist,其中 dist[i]表示从起点 1 到节点 i 的最短路径的长度

Dijkstra 算法

算法的基本流程:


  1. 初始化 dist[1] = 0,其余节点都为正无穷大

  2. 找到应该未标记的,dist[x]最小节点 x,然后标记节点 x

  3. 扫描节点 x 的所有出边(x,y,z),若 dist[y]>distp[x]+z,则使用 dist[x]+z 更新 dist[y]

  4. 重复上述 2-3,直到所有节点都被标记


不难发现,基于贪心,故只适用于边的长度为非负


当边长都为非负数的时候,全局最小值已经不能被其他节点更新,故在第一步中选出的节点 x 必然满足:dist[x]已经是起点到 x 的最短路径,进行不断的选择,标记,拓展,最终得到每个节点的最短路径的长度


package 最短路;
public class Dijkstra { /* * 参数adjMatrix:为图的权重矩阵,权值为-1的两个顶点表示不能直接相连 * 函数功能:返回顶点0到其它所有顶点的最短距离,其中顶点0到顶点0的最短距离为0 */ public int[] getShortestPaths(int[][] adjMatrix) { int[] result = new int[adjMatrix.length]; //用于存放顶点0到其它顶点的最短距离 boolean[] used = new boolean[adjMatrix.length]; //用于判断顶点是否被遍历 used[0] = true; //表示顶点0已被遍历 for(int i = 1;i < adjMatrix.length;i++) { result[i] = adjMatrix[0][i]; used[i] = false; }
for(int i = 1;i < adjMatrix.length;i++) { int min = Integer.MAX_VALUE; //用于暂时存放顶点0到i的最短距离,初始化为Integer型最大值 int k = 0; for(int j = 1;j < adjMatrix.length;j++) { //找到顶点0到其它顶点中距离最小的一个顶点 if(!used[j] && result[j] != -1 && min > result[j]) { min = result[j]; k = j; } } used[k] = true; //将距离最小的顶点,记为已遍历 for(int j = 1;j < adjMatrix.length;j++) { //然后,将顶点0到其它顶点的距离与加入中间顶点k之后的距离进行比较,更新最短距离 if(!used[j]) { //当顶点j未被遍历时 //首先,顶点k到顶点j要能通行;这时,当顶点0到顶点j的距离大于顶点0到k再到j的距离或者顶点0无法直接到达顶点j时,更新顶点0到顶点j的最短距离 if(adjMatrix[k][j] != -1 && (result[j] > min + adjMatrix[k][j] || result[j] == -1)) result[j] = min + adjMatrix[k][j]; } } } return result; }
public static void main(String[] args) { Dijkstra test = new Dijkstra(); int[][] adjMatrix = {{0,6,3,-1,-1,-1}, {6,0,2,5,-1,-1}, {3,2,0,3,4,-1}, {-1,5,3,0,2,3}, {-1,-1,4,2,0,5}, {-1,-1,-1,3,5,0}}; int[] result = test.getShortestPaths(adjMatrix); System.out.println("顶点0到图中所有顶点之间的最短距离为:"); for(int i = 0;i < result.length;i++) System.out.print(result[i]+" "); }}
复制代码


发布于: 刚刚阅读数: 2
用户头像

卷不死,就往…… 2021.10.19 加入

2019NOIP退役成员,华为云享专家,阿里云专家博主,csdn博主,努力进行算法分享,有问题欢迎私聊

评论

发布
暂无评论
单源最短路问题_算法_秋名山码民_InfoQ写作社区