最短路
求最短路：图中求某一点到一点的最短路。
dijkstra算法
单源最短路，权边为正时可以用迪杰斯特拉算法来解决
- 朴素版：时间复杂度O(n ^ 2)
- 堆优化版：时间复杂度O(mlogn)
算法：
戴克斯特拉算法(迪杰斯特拉算法)使用类似广度优先搜索的方法解决赋权图的单源最短路径问题。
原理：
该算法通过保留目前为止所找到的每个顶点v∈V从s到v的最短路径来工作。初始时，原点s的路径权重被赋为0(即原点的实际最短路径 = 0)。同时把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径，当算法结束时，d[v]中存储的便是s到v的最短路径，或者如果路径不存在的话是无穷大。
松弛操作是迪杰斯特拉算法的基础操作：如果存在一条从u到v的边，那么从s到v的一条新路径是将边w(u,v)∈E添加到从s到u的路径尾部来拓展一条从s到v的路径。这条路径的长度是d[u] + w(u,v)。如果这个值比目前一直的d[v]要小，那么可以用这个值来替代当前d[v]的值。松弛边的操作一直执行到所有的d[v]都代表s到v的最短路径的长度值。
算法维护两个顶点集合S和Q。集合S保留所有已知实际最短路径值的顶点，而集合Q则保留其他所有顶点。集合S初始状态为空，而后每一步都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d[u]值的顶点。当一个顶点u从Q中转移到了S中，算法对u的每条外接边w(u,v)进行松弛。
迪杰斯特拉算法演示
上图为迪杰斯特拉算法应用示意图。 起点以左下角的红点，目标是右上角的绿点，中间灰色的倒L型为障碍物。蓝色空圈表示”暂定”，用以搜索下一步；已经填充颜色的表示探访过，图中颜色以红到绿，越绿表示离起点越远。所有节点都被均匀的探索。
例题：
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 -1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 −1。
数据范围
1≤n≤500
1≤m≤10^5
图中涉及边长均不超过10000。输入样例：
3 3 1 2 2 2 3 1 1 3 4输出样例：
3
朴素版：
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int N = 510;
static int g[][] = new int[N][N];
static int dist[] = new int[N];
static boolean st[] = new boolean[N];
static int n,m;
static int max= (int) 1e9;
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String[] s = bufferedReader.readLine().split(" ");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
for (int i = 1; i <= n ; i++) {
Arrays.fill(g[i],max);
}
while(m-- > 0){
String[] s1 = bufferedReader.readLine().split(" ");
int a = Integer.parseInt(s1[0]);
int b = Integer.parseInt(s1[1]);
int c = Integer.parseInt(s1[2]);
g[a][b] = Math.min(g[a][b], c);
}
System.out.println(dijkstra());
}
private static int dijkstra(){
Arrays.fill(dist,max);
dist[1] = 0;
for (int i = 1; i < n ; i++) {
int t = -1;
for (int j = 1; j <= n ; j++) {
if (st[j]) continue;
if (t == -1 || dist[j] < dist[t]){
t = j;
}
}
if (t == n) break;
st[t] = true;
for (int j = 1; j <= n; j++) {
dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
}
}
if (dist[n] == max) return -1;
else return dist[n];
}
}堆优化版：
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
public class Main {
static int N= (int) (1e6);
static int h[] = new int[N];
static int e[] = new int[N];
static int ne[] = new int[N];
static int w[] = new int[N];
static int dist[] = new int[N];
static boolean st[] = new boolean[N];
static int n,m;
static int idx = 0;
static int INF = 0x3f3f3f3f;
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String[] s = bufferedReader.readLine().split(" ");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
Arrays.fill(h, -1);
while(m -- > 0) {
String[] s1 = bufferedReader.readLine().split(" ");
int a = Integer.parseInt(s1[0]);
int b = Integer.parseInt(s1[1]);
int c = Integer.parseInt(s1[2]);
add(a,b,c);
}
System.out.println(dijkstra());
}
private static void add(int a,int b,int c){
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++;
}
private static int dijkstra(){
PriorityQueue<PIIs> queue = new PriorityQueue<>();
Arrays.fill(dist, INF);
dist[1] = 0;
queue.add(new PIIs(0,1));
while (!queue.isEmpty()){
PIIs p = queue.poll();
int t = p.getSecond();
int distance = p.getFirst();
st[t] = true;
for (int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
if (dist[j] > distance + w[i]){
dist[j] = distance + w[i];
queue.add(new PIIs(dist[j],j));
}
}
} if(dist[n] == INF) return -1;
return dist[n];
}
}
class PIIs implements Comparable<PIIs>{
private int first;
private int second;
public PIIs(int first, int second) {
this.first = first;
this.second = second;
}
public int getFirst() {
return first;
}
public void setFirst(int first) {
this.first = first;
}
public int getSecond() {
return second;
}
public void setSecond(int second) {
this.second = second;
}
@Override
public int compareTo(PIIs o) {
return Integer.compare(first, o.first);
}
}解决负权边的算法
bellman-ford算法
它的原理是对图进行|V|-1次松弛操作，得到所有可能的最短路径。
算法：
贝尔曼-福特算法与迪杰斯特拉类似，都以松弛操作为基础，即估计的最短路径值渐渐地被更加准确的值替代，直至得到最优解。在两个算法中，计算时每个边之间的估计距离值都比真实值大，并且被新找到路径的最小长度替代。 然而，迪科斯彻算法以贪心法选取未被处理的具有最小权值的节点，然后对其的出边进行松弛操作；而贝尔曼-福特算法简单地对所有边进行松弛操作，共|V| - 1次，其中|V|是图的点的数量。在重复地计算中，已计算得到正确的距离的边的数量不断增加，直到所有边都计算得到了正确的路径。这样的策略使得贝尔曼-福特算法比迪科斯彻算法适用于更多种类的输入。
贝尔曼-福特算法的最多运行O(|V|·|E|)次，|V|和|E|分别是节点和边的数量)。
原理：
循环
每次循环操作实际上是对相邻节点的访问，第n次循环操作保证了所有深度为n的路径最短。由于图的最短路径最长不会经过超过|V| - 1条边，所以可知贝尔曼-福特算法所得为最短路径。
负边权操作
与迪科斯彻算法不同的是，迪科斯彻算法的基本操作“拓展”是在深度上寻路，而“松弛”操作则是在广度上寻路，这就确定了贝尔曼-福特算法可以对负边进行操作而不会影响结果。
负权环判定
因为负权环可以无限制的降低总花费，所以如果发现第n次操作仍可降低花销，就一定存在负权环。
优化：
循环的提前跳出
在实际操作中，贝尔曼-福特算法经常会在未达到|V| - 1次前就出解，|V| - 1其实是最大值。于是可以在循环中设置判定，在某次循环不再进行松弛时，直接退出循环，进行负权环判定。
队列优化
西南交通大学的段凡丁于1994年提出了用队列来优化的算法。松弛操作必定只会发生在最短路径前导节点松弛成功过的节点上，用一个队列记录松弛过的节点，可以避免了冗余计算。原文中提出该算法的复杂度为O(k|E|)，k是个比较小的系数，但该结论被证明不适于于所有情况。
C++示例
int SPFA(int s) {
std::queue<int> q;
bool inq[maxn] = {false};
for(int i = 1; i <= N; i++) dis[i] = 2147483647;
dis[s] = 0;
q.push(s); inq[s] = true;
while(!q.empty()) {
int x = q.front(); q.pop();
inq[x] = false;
for(int i = front[x]; i != 0 ; i = e[i].next) {
int k = e[i].v;
if(dis[k] > dis[x] + e[i].w) {
dis[k] = dis[x] + e[i].w;
if(!inq[k]) {
inq[k] = true;
q.push(k);
}
}
}
}
for(int i = 1; i <= N; i++) std::cout << dis[i] << ' ';
std::cout << std::endl;
return 0;
}例题：
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出
impossible。注意：图中可能 存在负权回路 。
输入格式
第一行包含三个整数 n,m,k
接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。
如果不存在满足条件的路径，则输出
impossible。数据范围
1≤n,k≤500
1≤m≤10000
任意边长的绝对值不超过 10000。输入样例：
3 3 1 1 2 1 2 3 1 1 3 3输出样例：
3
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int N = 510;
static int M = (int)1e5 + 10;
static int n,m,k;
static int[] dist=new int[N];
static Node[] list=new Node[M];
static int INF=0x3f3f3f3f;
static int[] back =new int[N];
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String[] s = bufferedReader.readLine().split(" ");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
k = Integer.parseInt(s[2]);
for(int i = 0;i < m;i++) {
String[] s1 = bufferedReader.readLine().split(" ");
int a = Integer.parseInt(s1[0]);
int b = Integer.parseInt(s1[1]);
int c = Integer.parseInt(s1[2]);
list[i] = new Node(a,b,c);
}
bellman_ford();
}
private static void bellman_ford() {
Arrays.fill(dist, INF);
dist[1] = 0;
for (int i = 0; i <k ; i++) {
back=Arrays.copyOf(dist,n + 1);
for (int j = 0; j < m ; j++) {
Node node = list[j];
int a = node.a;
int b = node.b;
int c = node.c;
dist[b] = Math.min(dist[b], back[a] + c);
}
}
if (dist[n] > INF / 2){
System.out.println("impossible");
}else {
System.out.println(dist[n]);
}
}
}
class Node{
int a,b,c;
public Node(int a, int b, int c) {
this.a = a;
this.b = b;
this.c = c;
}
}SPFA算法
最短路径快速算法
队列优化版的Bellman-Ford 算法，是一个用于求解有向带权图单源最短路径的算法。这一算法被认为在随机的稀疏图上表现出色，并且适用于带有负边权的图。然而SPFA在最坏情况的时间复杂度与 Bellman-Ford 算法相同，因此在非负边权的图中使用堆优化的Dijkstra 算法有可能优于SPFA。
算法：
给定一个有向带权图G=(V,E)和一个源点s，SPFA算法可以计算从s到图中每个节点v的最短路径。其基本思路与 Bellman-Ford 算法相同，即每个节点都被用作用于松弛其相邻节点的备选节点。但相较于 Bellman-Ford 算法，SPFA算法的改进之处在于它并不盲目地尝试所有节点，而是维护一个备选的节点队列，并且仅有节点被松弛后才会放入队列中。整个流程不断重复直至没有节点可以被松弛。
优化：
SPFA算法的性能很大程度上取决于用于松弛其他节点的备选节点的顺序。事实上，如果Q是一个优先队列，则这个算法将极其类似于迪杰斯特拉算法。然而尽管这一算法中并没有用到优先队列，仍有多种可用的技巧可以用来提升队列的质量，并且借此能够提高平均性能（但仍无法提高最坏情况下的性能）。其中，最著名的两种技巧通过重新调整Q中元素的顺序从而使得更靠近源点的节点能够被更早地处理。因此一旦实现了这两种技巧，Q将不再是一个先进先出队列，而更像一个链表或双端队列。
距离小者优先 （Small Label First(SLF)）。在伪代码的第十一行，将总是把v压入队列尾端修改为比较d(v) 和 d(front(Q))，并且在d(v)较小时将v压入队列的头端。这一技巧的伪代码如下（这部分代码插入在上面的伪代码的第十一行后)：
procedure Small-Label-First(G, Q)
if d(back(Q)) < d(front(Q)) then
u := pop back of Q
push u into front of Q距离大者置后 （Large Label Last(LLL)）。在伪代码的第十一行，我们更新队列以确保队列头端的节点的距离总小于平均，并且任何距离大于平均的节点都将被移到队列尾端。伪代码如下：
procedure Large-Label-Last(G, Q)
x := average of d(v) for all v in Q
while d(front(Q)) > x
u := pop front of Q
push u to back of Q例题：
最短路：
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出
impossible。数据保证不存在负权回路。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出
impossible。数据范围
1≤n,m≤10^5
图中涉及边长绝对值均不超过 10000输入样例：
3 3 1 2 5 2 3 -3 1 3 4输出样例：
2
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int N =(int)1e5 + 10;
static int n,m;
static int h[] = new int[N];
static int ne[] = new int[N];
static int e[] = new int[N];
static int w[] = new int[N];
static int dist[] = new int[N];
static boolean st[] = new boolean[N];
static int INF = 0x3f3f3f3f;
static int idx = 0;
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String[] s = bufferedReader.readLine().split(" ");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
Arrays.fill(h, -1);
while(m -- > 0) {
String[] s1 = bufferedReader.readLine().split(" ");
int a = Integer.parseInt(s1[0]);
int b = Integer.parseInt(s1[1]);
int c = Integer.parseInt(s1[2]);
add(a,b,c);
}
int t = spfa();
if(t == 0x3f3f3f3f) System.out.println("impossible");
else System.out.println(t);
}
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 spfa(){
Arrays.fill(dist, INF);
Queue<Integer> queue=new LinkedList<>();
dist[1] = 0;
queue.add(1);
st[1] = true;
while (!queue.isEmpty()){
int t = queue.poll();
st[t] = false;
for (int i = h[t]; i != -1 ; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
if (!st[j]) {
queue.add(j);
st[j] = true;
}
}
}
}
return dist[n];
}
}求负环：
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你判断图中是否存在负权回路。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
如果图中存在负权回路，则输出
Yes，否则输出No。数据范围
1≤n≤2000
1≤m≤10000,
图中涉及边长绝对值均不超过 10000输入样例：
3 3 1 2 -1 2 3 4 3 1 -4输出样例：
Yes
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static int N = (int)1e5 + 10;
static int n,m;
static int h[] = new int[N];
static int ne[] = new int[N];
static int e[] = new int[N];
static int w[] = new int[N];
static int dist[] = new int[N];
static int cnt[] = new int[N];
static boolean st[] = new boolean[N];
static int INF = 0x3f3f3f3f;
static int idx = 0;
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String[] s = bufferedReader.readLine().split(" ");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
Arrays.fill(h, -1);
while(m -- > 0) {
String[] s1 = bufferedReader.readLine().split(" ");
int a = Integer.parseInt(s1[0]);
int b = Integer.parseInt(s1[1]);
int c = Integer.parseInt(s1[2]);
add(a,b,c);
}
System.out.println(spfa());
}
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 String spfa(){
Arrays.fill(dist,INF);
Queue<Integer> queue=new LinkedList<>();
dist[1] = 0;
for (int i = 1; i <= n; i++) {
queue.add(i);
}
st[1] = true;
while (!queue.isEmpty()){
int t = queue.poll();
st[t] = false;
for (int i = h[t]; i != -1 ; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n){
return "Yes";
}
if (!st[j]) {
queue.add(j);
st[j] = true;
}
}
}
}
return "No";
}
}floyd算法
解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权(但不可存在负权回路)的最短路径问题，同时也被用于计算有向图的传递闭包。
时间复杂度O(N^3^)，空间复杂度O(N^2^)
原理：
Floyd算法的原理是动态规划。
设Di,j,k为从i到j的只以(1…k)集合中的节点为中间节点的最短路径的长度。
若最短路径经过点k，则D
i,j,k= Di,k,k-1+ Dk,j,k-1若最短路径不经过点k，则D
i,j,k= Di,j,k-1
因此，Di,j,k = min(Di,j,k-1，Di,k,k-1 + Dk,j,k-1)
在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。
例题：
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。
再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出
impossible。数据保证图中不存在负权回路。
输入格式
第一行包含三个整数 n,m,k。
接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 xx 到点 yy 的有向边，边长为 zz。
接下来 kk 行，每行包含两个整数 x,y，表示询问点 x 到点 y 的最短距离。
输出格式
共 kk 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出
impossible。数据范围
1≤n≤200,
1≤k≤n^2
1≤m≤20000
图中涉及边长绝对值均不超过 10000。输入样例：
3 3 2 1 2 1 2 3 2 1 3 1 2 1 1 3输出样例：
impossible 1
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 210;
static int n,m,q;
static int INF = 0x3f3f3f3f;
static int d[][] = new int[N][N];
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String[] s = bufferedReader.readLine().split(" ");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
q = Integer.parseInt(s[2]);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
d[i][j] = i == j ? 0 : INF;
}
}
while (m-- > 0){
String[] s1 = bufferedReader.readLine().split(" ");
int a = Integer.parseInt(s1[0]);
int b = Integer.parseInt(s1[1]);
int c = Integer.parseInt(s1[2]);
d[a][b] = Math.min(d[a][b],c);
}
floyd();
while (q-- > 0){
String[] s2 = bufferedReader.readLine().split(" ");
int a = Integer.parseInt(s2[0]);
int b = Integer.parseInt(s2[1]);
int t = d[a][b];
if (t > INF / 2){
System.out.println("impossible");
}else {
System.out.println(t);
}
}
}
public static void floyd(){
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
d[i][j] = Math.min(d[i][j],d[i][k] + d[k][j]);
}
}
}
}
}- 本文作者： ShanTianQi
- 本文链接： https://stq555.com/2022/02/27/%E6%9C%80%E7%9F%AD%E8%B7%AF/index.html
- 版权声明：本博客所有文章均采用 BY-NC-SA 许可协议，转载请注明出处！
