做电商网站用什么框架,wordpress实现会员中心,公司网站用什么系统,备案 网站名称涉及到行业一图胜千言 单源最短路径
正权值 朴素Dijkstra
dijkstra算法思想是维护一个永久集合U#xff0c;全部点集合V。
循环n -1次
从源点开始#xff0c;在未被访问的节点中#xff0c;选择距离源点最近的节点 t。
以节点 t 为中间节点#xff0c;更新从起点到其他节点的最短…一图胜千言 单源最短路径
正权值 朴素Dijkstra
dijkstra算法思想是维护一个永久集合U全部点集合V。
循环n -1次
从源点开始在未被访问的节点中选择距离源点最近的节点 t。
以节点 t 为中间节点更新从起点到其他节点的最短距离。对于每个节点 j比较当前的 distance[j] 和 distance[t] graph[t][j]取较小值作为新的 distance[j]。
将节点 t 标记为已访问。 【例题】
给定一个 n 个点 m 条边的有向图图中可能存在重边和自环所有边权均为正值。
请你求出 1 号点到 n 号点的最短距离如果无法从 1 号点走到 n 号点则输出 −1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边边长为 z。
输出格式
输出一个整数表示 1 号点到 n 号点的最短距离。
如果路径不存在则输出 −1。
数据范围
1≤n≤500, 1≤m≤ 1 0 5 10^5 105, 图中涉及边长均不超过10000。
输入样例
3 3
1 2 2
2 3 1
1 3 4输出样例
3import java.io.*;
import java.util.*;
public class Main {static final int MAX_NUM 2147483647 / 2;static final int N 510;static final int M 100010;static int[][] graph new int[N][N];static int[] used new int[N];static int[] distance new int[N];static int n, m;public static void main(String[] args) throws Exception {BufferedReader br new BufferedReader(new InputStreamReader(System.in));String row1 br.readLine();String[] items row1.split( );n Integer.parseInt(items[0]);m Integer.parseInt(items[1]);//初始化将graph全初始化为无穷大for(int i 0; i n; i) {for(int j 0; j n; j) {graph[i][j] MAX_NUM;}}//存储邻接矩阵while(m-- 0) {String row br.readLine();String[] data row.split( );int x Integer.parseInt(data[0]);int y Integer.parseInt(data[1]);int z Integer.parseInt(data[2]);//因为可能会有重边只保存最小的graph[x][y] Math.min(graph[x][y], z);}System.out.print(dijkstra());br.close();}public static int dijkstra() {//将距离初始化为最大值for(int i 0; i n; i) {distance[i] MAX_NUM;}distance[1] 0;for(int i 0; i n - 1; i) {int t -1;//寻找与永久集合中权值最小的结点for(int j 1; j n; j) {if(used[j] 0 (t -1 || distance[t] distance[j])) {t j;}}//根据t计算从初结点到后序结点和从t结点到后序结点那个值更小for(int j 1; j n; j) {distance[j] Math.min(distance[j], distance[t] graph[t][j]);}//标记t为用过结点used[t] 1;}if(distance[n] MAX_NUM) {return -1;} else {return distance[n];}}
}正权值 堆优化Dijkstra
堆优化版通过优先队列堆来快速找到距离源点最近的节点每次从堆中取出最小元素的时间复杂度为 (O(\log n))而遍历所有边的时间复杂度为 (O(m))。
朴素版 Dijkstra适用于稠密图即边的数量接近节点数量的平方的情况。因为在稠密图中邻接矩阵可以更方便地存储和访问图的信息。
堆优化版 Dijkstra适用于稀疏图即边的数量远小于节点数量的平方的情况。在稀疏图中邻接表可以节省存储空间而优先队列可以提高寻找最小距离节点的效率。
核心步骤
当堆不为空时从堆中取出距离源点最近的节点 no 及其距离 d。
如果节点 no 已经确定最短路径则跳过该节点。
标记节点 no 已经确定最短路径。
遍历节点 no 的所有邻接节点 j如果通过节点 no 到达节点 j 的距离比当前记录的距离更短则更新 distance[j] 的值并将节点 j 及其新的距离加入堆中。
【例题】
给定一个 n 个点 m 条边的有向图图中可能存在重边和自环所有边权均为非负值。
请你求出 1 号点到 n 号点的最短距离如果无法从 1 号点走到 n 号点则输出−1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边边长为 z。
输出格式
输出一个整数表示 1 号点到 n 号点的最短距离。
如果路径不存在则输出 −1。
数据范围
1≤n,m≤1.5× 1 0 5 10^5 105, 图中涉及边长均不小于 0且不超过 10000。 数据保证如果最短路存在则最短路的长度不超过 1 0 9 10^9 109。
输入样例
3 3
1 2 2
2 3 1
1 3 4输出样例
3import java.io.*;
import java.util.*;
public class Main {static final int N 100010;static final int MAX_NUM 2147483647 / 2;static int[] head new int[N];static int[] value new int[N];static int[] weight new int[N];static int[] ne new int[N];static int[] used new int[N];static int[] distance new int[N];static int n, m, idx;public static void main(String[] args) throws Exception{BufferedReader br new BufferedReader(new InputStreamReader(System.in));String[] items br.readLine().split( );n Integer.parseInt(items[0]);m Integer.parseInt(items[1]);//初始化head数组Arrays.fill(head, -1);//读取m次数据while(m-- 0) {String[] data br.readLine().split( );int x Integer.parseInt(data[0]);int y Integer.parseInt(data[1]);int z Integer.parseInt(data[2]);add(x, y, z);}System.out.print(dijkstra());}static void add(int from, int to, int w) {value[idx] to;weight[idx] w;ne[idx] head[from];head[from] idx;}static int dijkstra() {//初始化距离Arrays.fill(distance, MAX_NUM);distance[1] 0;PriorityQueueint[] heap new PriorityQueue((a, b) - a[0] - b[0]);heap.offer(new int[]{0, 1});while(!heap.isEmpty()) {//从堆中取出离源点距离最小的元素int[] item heap.poll();int d item[0];int no item[1];//判断该点是否已经在永久集合中if(used[no] 1) {continue;}used[no] 1;//根据这一点去计算其他通过该点达到的结点的距离是否更新for(int i head[no]; i ! -1; i ne[i]) {//结点编号int j value[i];if(distance[j] distance[no] weight[i]) {distance[j] distance[no] weight[i];heap.offer(new int[]{distance[j], j});}}}return distance[n] MAX_NUM ? -1 : distance[n];}
}负权值 bellman-ford
核心逻辑
初始化
将 distance 数组的所有元素初始化为无穷大 MAX_NUM表示初始时所有节点到源点的距离都是未知的。将源点节点 1的距离 distance[1] 初始化为 0因为源点到自身的距离为 0。
迭代更新距离
进行 k 次迭代每次迭代的目的是保证找到的最短路径最多经过 k 条边。在每次迭代之前先将 distance 数组复制到 temp 数组中。这一步是为了避免在更新距离时出现数据串联的问题确保每次更新都是基于上一次迭代的结果。遍历 edges 列表中的每一条边 e对于每条边尝试通过这条边来更新终点 e.to 的最短距离。具体来说比较当前 distance[e.to] 和 temp[e.from] e.weight 的大小取较小值作为新的 distance[e.to]。对每一条边进行松弛操作
如果经历至多n - 1次迭代能够收敛于稳定否则一定会有负环 负环每走一次都会使得距离变短导致无穷循环
对于由n个结点构成的链路最多有n-1跳所以超过n - 1跳就一定会有负环存在且不可能是最短路径 【例题】
给定一个 n 个点 m 条边的有向图图中可能存在重边和自环 边权可能为负数。
请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离如果无法从 1 号点走到 n 号点输出 impossible。
注意图中可能 存在负权回路 。
输入格式
第一行包含三个整数 n,m,k。
接下来 mm 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边边长为 z。
点的编号为 1∼n。
输出格式
输出一个整数表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。
如果不存在满足条件的路径则输出 impossible。
数据范围
1≤n,k≤500, 1≤m≤10000, 1≤x,y≤n 任意边长的绝对值不超过 10000。
输入样例
3 3 1
1 2 1
2 3 1
1 3 3输出样例
3import java.io.*;
import java.util.*;
public class Main {static class edge {public int from;public int to;public int weight;public edge(int from, int to, int weight) {this.from from;this.to to;this.weight weight;}}static final int N 510;static final int MAX_NUM 2147483647 / 2;static int n, m, k;static Listedge edges new ArrayList();static int[] distance new int[N];public static void main(String[] args) throws Exception{BufferedReader br new BufferedReader(new InputStreamReader(System.in));String[] items br.readLine().split( );n Integer.parseInt(items[0]);m Integer.parseInt(items[1]);k Integer.parseInt(items[2]);while (m-- 0) {String[] data br.readLine().split( );int from Integer.parseInt(data[0]);int to Integer.parseInt(data[1]);int weight Integer.parseInt(data[2]);edges.add(new edge(from, to, weight));}//调用bellman ford算法bellmanFord();}public static void bellmanFord() {//初始化distanceArrays.fill(distance, MAX_NUM);distance[1] 0;//k次循环保证最多经过k条边的距离for (int i 0; i k; i) {//拷贝distance数组避免数据串联int[] temp Arrays.copyOf(distance, distance.length);for (edge e : edges) {distance[e.to] Math.min(distance[e.to], temp[e.from] e.weight );}}//判断distance[n]的大小, MAX_NUM / 2 是终点前的负值边对对distance[n]产生影响会使最大值减少 k * weight if (distance[n] MAX_NUM / 2) {System.out.println(impossible);} else {System.out.println(distance[n]);}}
}负权值 SPFA
Bellman - Ford 算法的时间复杂度是 (O(k m))其中 k 通常是节点数 n也就是在一般情况下时间复杂度为 (O(n m))。这是因为在每一轮迭代中它都会对图中的每一条边进行松弛操作不管这条边是否能真正更新节点的最短距离。在很多情况下大量的松弛操作是不必要的导致算法效率较低。
当图的规模较大时Bellman - Ford 算法的性能会变得很差。而 SPFAShortest Path Faster Algorithm算法就是为了优化 Bellman - Ford 算法的效率而提出的它通过队列来减少不必要的松弛操作从而在很多情况下能显著提高算法的执行效率。
SPFA 算法的核心思想是利用队列来维护待处理的节点。只有当一个节点的最短距离被更新时才将其加入队列等待后续对其出边进行松弛操作。这样就避免了 Bellman - Ford 算法中对所有边进行无意义的松弛操作从而减少了不必要的计算。
初始化
定义常量 N 表示节点的最大数量MAX_NUM 表示无穷大。初始化邻接表相关数组 head、value、weight、ne 用于存储图的信息。初始化队列 queue队头指针 hh 和队尾指针 tt。初始化 distance 数组将所有节点的距离初始化为无穷大源点节点 1的距离初始化为 0。初始化 inQueue 数组用于标记节点是否在队列中初始时所有节点都不在队列中。
入队操作
将源点节点 1加入队列并标记其在队列中。
队列处理 当队列不为空时从队头取出一个节点 t并标记该节点不在队列中。 遍历节点t的所有出边 对于每一条出边 (t, j)如果通过节点 t 到达节点 j 的距离比当前记录的 distance[j] 更短则更新 distance[j] 的值。如果节点 j 不在队列中则将其加入队列并标记其在队列中。
【例题】
给定一个 n 个点 m 条边的有向图图中可能存在重边和自环 边权可能为负数。
请你求出 1 号点到 n 号点的最短距离如果无法从 1 号点走到 n 号点则输出 impossible。
数据保证不存在负权回路。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边边长为 z。
输出格式
输出一个整数表示 1 号点到 n 号点的最短距离。
如果路径不存在则输出 impossible。
数据范围
1≤n,m≤ 1 0 5 10^5 105, 图中涉及边长绝对值均不超过 10000。
输入样例
3 3
1 2 5
2 3 -3
1 3 4输出样例
2import java.io.*;
import java.util.*;
public class Main {static final int N 100010;static final int MAX_NUM 2147483647 / 2;static int[] head new int[N];static int[] value new int[N];static int[] weight new int[N];static int[] ne new int[N];static int hh 0, tt -1, idx 0, n, m;static int[] queue new int[N];static int[] distance new int[N];static boolean[] inQueue new boolean[N];public static void main(String[] args) throws Exception{BufferedReader br new BufferedReader(new InputStreamReader(System.in));String[] row1 br.readLine().split( );n Integer.parseInt(row1[0]);m Integer.parseInt(row1[1]);//初始化head数组Arrays.fill(head, -1);//m次读入while(m-- 0) {String[] data br.readLine().split( );int x Integer.parseInt(data[0]);int y Integer.parseInt(data[1]);int z Integer.parseInt(data[2]);add(x, y, z);}spfa();br.close();}static void add(int from, int to, int w) {value[idx] to;weight[idx] w;ne[idx] head[from];head[from] idx;}static void spfa() {//初始化distance数组Arrays.fill(distance, MAX_NUM);distance[1] 0;//将第一个数加入队列queue[tt] 1;//更新1的状态inQueue[1] true;while(hh tt) {//从队头取出一个数int t queue[hh];//更新队头元素的状态inQueue[t] false;//遍历该结点的所有出边for(int i head[t]; i ! -1; i ne[i]) {int j value[i];if(distance[j] distance[t] weight[i]) {distance[j] distance[t] weight[i];if(inQueue[j] false) {queue[tt] j;inQueue[j] true;}}}}if(distance[n] MAX_NUM) {System.out.print(impossible);} else {System.out.print(distance[n]);}}
}多源最短路径
Floyd
算法原理
Floyd 算法通过一个三层循环来逐步更新图中各顶点对之间的最短路径。设图中有 n 个顶点用邻接矩阵 (graph[i][j]) 表示顶点 i 到顶点 j 的边权若 i 和 j 之间没有边则权值为无穷大。
定义一个三维数组 (dist[k][i][j]) 表示从顶点 i 到顶点 j 经过编号不超过 k 的顶点的最短路径长度也可简化为二维数组 (dist[i][j]) 在每次迭代中直接更新。
迭代过程分析
初始状态在算法开始时(dist[0][i][j]graph[i][j]) 即不经过任何中间顶点时顶点 i 到顶点 j 的距离就是它们之间的边权。这是符合实际情况的因为没有中间节点参与时两点间距离就是直接相连的边权若不相连则为无穷大。第 k 次迭代在第 k 次迭代中对于每一对顶点 ((i, j)) 考虑是否经过顶点 k 会使 i 到 j 的路径更短。即比较 (dist[k - 1][i][j]) 不经过顶点 k 时 i 到 j 的最短路径和 (dist[k - 1][i][k]dist[k - 1][k][j]) 经过顶点 k 从 i 到 k 再从 k 到 j 的路径长度 的大小。取较小值作为 (dist[k][i][j]) 。
这种比较是合理的因为如果存在一条从 i 到 j 经过顶点 k 的更短路径那么必然是由从 i 到 k 的最短路径和从 k 到 j 的最短路径组成。而在第 k 次迭代时我们已经知道了不经过顶点 k 即经过编号小于 k 的顶点子集 时从 i 到 k 和从 k 到 j 的最短路径分别为 (dist[k - 1][i][k]) 和 (dist[k - 1][k][j]) 。通过这种比较和更新我们能得到经过编号不超过 k 的顶点时 i 到 j 的最短路径。
【例题】
给定一个 n 个点 m 条边的有向图图中可能存在重边和自环边权可能为负数。
再给定 k 个询问每个询问包含两个整数 x 和 y表示查询从点 x 到点 y 的最短距离如果路径不存在则输出 impossible。
数据保证图中不存在负权回路。
输入格式
第一行包含三个整数 n,m,k。
接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边边长为 z。
接下来 k 行每行包含两个整数 x,y表示询问点 xx 到点 y 的最短距离。
输出格式
共kk 行每行输出一个整数表示询问的结果若询问两点间不存在路径则输出 impossible。
数据范围
1≤n≤200, 1≤k≤n2 1≤m≤20000, 图中涉及边长绝对值均不超过 10000。
输入样例
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3输出样例
impossible
1import java.io.*;
import java.util.*;
public class Main {static final int MAX_NUM 2147483647 / 2;static final int N 210;static int n, m;static int[][] graph new int[N][N];public static void main(String[] args) throws Exception {BufferedReader br new BufferedReader(new InputStreamReader(System.in));String[] row1 br.readLine().split( );n Integer.parseInt(row1[0]);m Integer.parseInt(row1[1]);int q Integer.parseInt(row1[2]);//对邻接矩阵进行初始化for(int i 1; i n; i) {for(int j 1; j n; j) {if(i j) {graph[i][j] 0;} else {graph[i][j] MAX_NUM;}}}for(int i 1; i m; i) {String[] data br.readLine().split( );int a Integer.parseInt(data[0]);int b Integer.parseInt(data[1]);int c Integer.parseInt(data[2]);graph[a][b] Math.min(graph[a][b], c);}floyd();//q次询问while(q-- 0) {String[] fromTo br.readLine().split( );int from Integer.parseInt(fromTo[0]);int to Integer.parseInt(fromTo[1]);if(graph[from][to] MAX_NUM / 2) {System.out.println(impossible);} else {System.out.println(graph[from][to]);}}}static void floyd() {for(int k 1; k n; k) {for(int i 1; i n; i) {for(int j 1; j n; j) {graph[i][j] Math.min(graph[i][j], graph[i][k] graph[k][j]);}}}}
}
