脚本宝典收集整理的这篇文章主要介绍了最短路问题，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

最短路问题

朴素版Dijkstra(稠密图)

	s数组，当前已经确定最短路径的点
1	dis[1] = 0, dis[i] = 正无穷
2	for(int i = 0; i <= n; i ++)  
		t <- 不在s中距离最近的点
		s <- t 用t更新其他点的距离（从t出去的所有的边组成的路径能不能更新其		  他点的距离 
		1 -> t -> x;
		1 ------> x;如果前一种情况的距离小于第二种就可以更新
		dis[x] > dis[t] + w;
									

给定一个 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。

输入样例：

3 3
1 2 2
2 3 1
1 3 4

输出样例：

3

#include <bits/stdc++.h>

using namespace std;
const int N = 510;

int g[N][N];
int dist[N];
bool st[N];
int n, m;
int dijkstra(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    for(int i = 0; i < n; i ++)
    {
        int t = -1;
        for(int j = 1; j <= n; j ++)
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        
        
        st[t] = true;
        
        for(int j = 1; j <= n; j ++){
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
    }
    
    if(dist[n] == 0x3f3f3f3f) return -1;
        
    return dist[n];
}

int main(){
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while(m --){
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b], c);
    }
    cout << dijkstra();
    return 0;
}

堆优化版Dijkstra（稀疏图）

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1−1。

输入格式

第一行包含整数 n 和 m。

接下来 mm 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1号点到 n 号点的最短距离。

如果路径不存在，则输出 −1。

数据范围

1≤n,m≤1.5×105 图中涉及边长均不小于 0，且不超过 10000。 数据保证：如果最短路存在，则最短路的长度不超过 109。

输入样例：

3 3
1 2 2
2 3 1
1 3 4

输出样例：

3

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e6 + 10;

int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});//前一个是距离，后一个是

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    cout << dijkstra() << endl;

    return 0;
}

Bellman_Ford(极少数情况，图中不存在负权回路(负环))

1.for(int i = 1; i <= n; i ++)
2.备份dist防止串联
3.for 所有边 a,b,w
4.dist[b] = min(dist[b], dist[a] + w)(松弛操作)
 最后满足dist[b] <= dist[a] + w(三角不等式)
 
 此算法不能存在负权回路
 是否存在负权回路的验证方法
 1.迭代K次(不超过k条边)的最短路的距离
 2.如果第n次迭代时更新了某些边(说明存在一条最短路径有n条边，n+1个点)(说明一定存在负权回路)
 	一共有n个点，但是出现了n个边，根据抽屉原理，说明一定有回路存在

有边数限制的最短路

给定一个 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

#include <bits/stdc++.h>

using namespace std;
const int N = 510, M = 10010;
struct Edge
{
    int a, b, w;
}edges[M];

int dist[N];
int backup[N];
int n, m, k;

void bellman_ford(){
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    
    for(int i = 0; i < k; i ++ ){
        memcpy(backup, dist, sizeof dist);
        for(int j = 0; j < m; j ++){
            auto t = edges[j];
            dist[t.b] = min(dist[t.b], backup[t.a] + t.w);
        }
    }
    
}

int main(){
    cin >> n >> m >> k;
    for(int i = 0; i < m; i ++){
        int a, b, w;
        cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }
    
    bellman_ford();
    
    if(dist[n] > 0x3f3f3f3f / 2) puts("impossible");
    else cout << dist[n] << endl;
    
    return 0;
}

SPFA（常用）

Floyd（多源最短路）

脚本宝典总结

以上是脚本宝典为你收集整理的最短路问题全部内容，希望文章能够帮你解决最短路问题所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。