优购物官方网站手机版,睿达科网络 网站建设,深圳市网站建设有补贴吗,峰聘网360建筑网你好#xff0c;我是Hasity。
今天分享的内容#xff1a;Dijkstra求最短路这个题目
Dijkstra求最短路I
题目描述
给定一个 n个点 m 条边的有向图#xff0c;图中可能存在重边和自环#xff0c;所有边权均为正值。
请你求出 1 号点到 n号点的最短距离#xff0c;如果无…你好我是Hasity。
今天分享的内容Dijkstra求最短路这个题目
Dijkstra求最短路I
题目描述
给定一个 n个点 m 条边的有向图图中可能存在重边和自环所有边权均为正值。
请你求出 1 号点到 n号点的最短距离如果无法从 1 号点走到 n 号点则输出 −1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边边长为 z。
输出格式
输出一个整数表示 1 号点到 n号点的最短距离。
如果路径不存在则输出 −1。
数据范围
1≤n≤500, 1≤m≤105, 图中涉及边长均不超过10000。
示例 思路分析
迪杰斯特拉算法采用的是一种贪心的策略。求源点到其余各点的最短距离步骤如下
用一个 dist 数组保存源点到其余各个节点的距离dist[i] 表示源点到节点 i 的距离。初始时dist 数组的各个元素为无穷大。 用一个状态数组 state 记录是否找到了源点到该节点的最短距离state[i] 如果为真则表示找到了源点到节点 i 的最短距离state[i] 如果为假则表示源点到节点 i 的最短距离还没有找到。初始时state 各个元素为假。 源点到源点的距离为 0。即dist[1] 0。 遍历 dist 数组找到一个节点这个节点是没有确定最短路径的节点中距离源点最近的点。假设该节点编号为 i。此时就找到了源点到该节点的最短距离state[i] 置为 1。 遍历 i 所有可以到达的节点 j如果 dist[j] 大于 dist[i] 加上 i - j 的距离即 dist[j] dist[i] w[i][j]w[i][j] 为 i - j 的距离 则更新 dist[j] dist[i] w[i][j]。 重复 3 4 步骤直到所有节点的状态都被置为 1。 更新与序号1相连接的节点(2,3,4)的dist离源点1距离最近的状态为0的节点是2将节点2的state改为1更新与序号2相连接的节点5的dist 离源点1距离最近的状态为0的的节点是4将节点4的state改为1更新与序号4相连接的节点5的dist 离源点1距离最近的状态为0的的节点是3将节点3的state改为1更新与序号3相连接的节点4的dist 离源点1距离最近的状态为0的的节点是5将节点5的state改为1更新与序号5相连接的节点的的dist没有也需要遍历一遍 此时 dist 数组中就保存了源点到其余各个节点的最短距离。 思考我们用什么数据结构表示图的任意顶点之间的连接关系呢
邻接表和邻接矩阵是图的两种常用存储表示方式用于记录图中任意两个顶点之间的连通关系包括权值。
对于无向图 graph和有向图digraph 选择一邻接表
无向图 graph 表示 有向图 digraph 表示 选择二邻接矩阵
无向图 graph 表示 有向图 digraph 表示 由题中的1≤n≤500的数据量较小我们采用邻接矩阵的方法代码更容易实现
关于领接表的优缺点大家可以看这一篇文章
代码实现
import java.util.*;
public class Main{static int N 510,n,m, max 0x3f3f3f3f;static int[][] g new int[N][N];//存每个点之间的距离static int[] dist new int[N];//存每个点到起点之间的距离static boolean[] st new boolean[N];//存已经确定了最短距离的点public static int dijkstra(){Arrays.fill(dist,max);//将dist数组一开始赋值成较大的数dist[1] 0; //首先第一个点是零//从0开始,遍历n次一次可以确定一个最小值for(int i 0 ; i n ; i ){ int t -1; //t这个变量,准备来说就是转折用的for(int j 1 ; j n ; j ){/**** 因为数字是大于1的所以从1开始遍历寻找每个数* 如果s集合中没有这个数* 并且t -1表示刚开始 或者 后面的数比我心找的数距离起点的距离短* 然后将j 的值赋值给 t***/if(!st[j] (t -1 || dist[j] dist[t])){t j; }}st[t] true;//表示这个数是已经找到了确定了最短距离的点//用已经确认的最短距离的点来更新后面的点//就是用1到t的距离加上t到j的距离来更新从1到j的长度for(int j 1 ; j n ; j ){//dist[j] Math.min(dist[j],dist[t] g[t][j]);}}//如果最后n的长度没有改变输出-1没有找到否则输出最短路nif(dist[n] max) return -1;else return dist[n];}public static void main(String[] args){Scanner scan new Scanner(System.in);n scan.nextInt();m scan.nextInt();//将他们每个点一开始赋值成一个较大的值for(int i 1 ; i n ; i ){Arrays.fill(g[i],max);}while(m -- 0){int a scan.nextInt();int b scan.nextInt();int c scan.nextInt();g[a][b] Math.min(g[a][b],c);//这个因为可能存在重边所以泽出最短的}int res dijkstra();System.out.println(res);}
}Dijkstra求最短路 II
题目描述
给定一个 n个点 m 条边的有向图图中可能存在重边和自环所有边权均为正值。
请你求出 1 号点到 n号点的最短距离如果无法从 1 号点走到 n 号点则输出 −1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边边长为 z。
输出格式
输出一个整数表示 1 号点到 n号点的最短距离。
如果路径不存在则输出 −1。
数据范围
1≤n,m≤1.5×105 图中涉及边长均不小于 0且不超过 10000。 数据保证如果最短路存在则最短路的长度不超过 109。
示例 思路分析
这道题和上一道没有什么区别差别只有数据范围的变化 第一题 1≤n≤500, 1≤m≤105, 图中涉及边长均不超过10000。 第二题 1≤n,m≤1.5×105 图中涉及边长均不小于 0且不超过 10000。 数据保证如果最短路存在则最短路的长度不超过 109。 我们可以对比发现节点n的取值变大了那么按照之前的时间复杂度O(n2)是肯定会超时的所以我们需要降低时间复杂度使用优先队列小根堆解决并且随着n的取值变大我们使用领接表来替代邻接矩阵存储图之间的关系
第一题找到未标记的离源点最近的点 O(n2) for(int i 0 ; i n ; i ){ int t -1; //t这个变量,准备来说就是转折用的for(int j 1 ; j n ; j ){/**** 因为数字是大于1的所以从1开始遍历寻找每个数* 如果s集合中没有这个数* 并且t -1表示刚开始 或者 后面的数比我心找的数距离起点的距离短* 然后将j 的值赋值给 t***/if(!st[j] (t -1 || dist[j] dist[t])){t j; }}
算法的主要耗时的步骤是从dist 数组中选出没有确定最短路径的节点中距离源点最近的点 t。只是找个最小值而已没有必要每次遍历一遍dist数组。在一组数中每次能很快的找到最小值很容易想到使用优先队列小根堆 代码实现
import java.util.*;
class PIIs implements ComparablePIIs{private int first;//距离值private int second;//点编号public int getFirst(){return this.first;}public int getSecond(){return this.second;}public PIIs(int first,int second){this.first first;this.second second;}Overridepublic int compareTo(PIIs o) {// TODO 自动生成的方法存根return Integer.compare(first, o.first);}
}
public class Main{static int N 150010,n,m,idx,max 0x3f3f3f3f;static int [] h new int[N],e new int[N],ne new int[N],w new int[N];static int[] dist new int[N];static boolean[] st new boolean[N];public static void add(int a,int b,int c){e[idx] b;w[idx] c;ne[idx] h[a];h[a] idx;}public static int dijkstra(){//优先队列保证每次取出都是最小值//维护当前未在st中标记过且离源点最近的点 小跟堆PriorityQueuePIIs queue new PriorityQueuePIIs();Arrays.fill(dist, max);dist[1] 0;queue.add(new PIIs(0,1));while(!queue.isEmpty()){//1、找到当前未在s中出现过且离源点最近的点PIIs p queue.poll();int distance p.getFirst();int t p.getSecond();if(st[t]) continue;//2、将该点进行标记st[t] true;//3、用t更新其他点的距离for(int i h[t];i ! -1;i ne[i])//不要被这个遍历误导这只是一个遍历循环而已i只是下一个点的下标{int j e[i];// i只是个下标e中在存的是i这个下标对应的点和值。if(dist[j] distance w[i]){dist[j] distance w[i];queue.add(new PIIs(dist[j],j));}}}if(dist[n] max) return -1;return dist[n];}public static void main(String[] args){Scanner scan new Scanner(System.in);n scan.nextInt();m scan.nextInt();Arrays.fill(h,-1);while(m -- 0){int a scan.nextInt();int b scan.nextInt();int c scan.nextInt();add(a,b,c);}int res dijkstra();System.out.println(res);}
}
总结
迪杰斯特拉算法适用于求正权有向图中源点到其余各个节点的最短路径。注意图中可以有环但不能有负权边。
例如如下图就不能使用迪杰斯特拉算法求节点 1 到其余各个节点的最短距离。
