图论--最短路问题

这篇具有很好参考价值的文章主要介绍了图论--最短路问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

图论–最短路问题

邻接表-链式前向星

/*
e[idx]:存储点的编号
w[idx]:存储边的距离(权重)
*/
void add(int a, int b, int c) {
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c
    h[a] = idx ++;
}

1.拓扑排序

给定一个 n 个点 m 条边的有向图,点的编号是 11 到 n,图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出 −1−1。

若一个由图中所有点构成的序列 A 满足:对于图中的每条边 (x,y),x在 A中都出现在 y 之前,则称 A是该图的一个拓扑序列。

输入格式

第一行包含两个整数 n 和 m。

接下来 m 行,每行包含两个整数 x 和 y,表示存在一条从点 x 到点 y的有向边 (x,y)。

输出格式

共一行,如果存在拓扑序列,则输出任意一个合法的拓扑序列即可。

否则输出 −1−1。

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

using namespace std;

const int N = 1e5 + 10;

int n, m;

// 队列
int q[N], hh, tt = -1;

// 邻接表
int e[N], idx, ne[N], h[N];

// 入度
int d[N];

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

bool topsort() {
    for (int i = 1; i <= n; i ++)
        if (!d[i])
            q[++ tt] = i;
    
    while (hh <= tt) {
        int tmp = q[hh ++];
        
        for (int i = h[tmp]; i != -1; i = ne[i]) {
            int j = e[i];
            d[j] --;
            if (!d[j])
                q[++ tt] = j;
        }
    }
    
    if (tt == n-1)  
        return true;
    return false;
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while (m --) {
        int a, b;
        cin >> a >> b;
        add(a, b);
        d[b] ++;
    }
    if (topsort()) 
        for (int i = 0; i < n; i ++)
            cout << q[i] << ' ';
    else    
        cout << -1;
        
    return 0;
}

2.Dijkstra求最短路

稠密图(边很多)——邻接矩阵

所有边权都是正数,单源最短路

  • 初始化到每个节点距离为无穷inf,初识节点距离dist[1] = 0

  • 迭代n轮

  • 每次从未标记的节点中选择距离出发点最近的节点,标记,收录到最优路径集合中

  • 计算刚加入节点A的临近节点B的距离(不包含标记的节点)。若节点A的距离加节点A到B的距离小于节点B的距离,则更新节点B的距离。

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

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

输入格式

第一行包含整数 n 和 m。

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

输出格式

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

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

#include <iostream>
#include <algorithm>    
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 505;

int n, m;

// 标记
int st[N];
// 距离
int dist[N];
// 邻接矩阵
int g[N][N];

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] = 1;
        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() {
    memset(g, 0x3f, sizeof g);
    
    scanf("%d%d", &n, &m);
    
    for (int i = 1; i <= n; i ++)
        g[i][i] = 0;
        
    while (m --) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        g[x][y] = min(g[x][y], z);
    }
    
    int ans = dijkstra();
    printf("%d", ans);
    
    return 0;
}

堆优化

稀疏图(点很多)——邻接表

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

using namespace std;

typedef pair<int, int> pii;

const int N = 1e6 + 10;

int n, m;

// 标记,避免自环
int st[N]; 

// 邻接表
int e[N], h[N], ne[N], w[N], idx;

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

int dist[N];

int dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    // 小根堆 {边权(距离),编号}
    priority_queue<pii, vector<pii>, greater<pii>> heap;
    heap.push({0, 1});
    while (!heap.empty()) {
        int v = heap.top().second, distance = heap.top().first;
        heap.pop();
        if (st[v])  
            continue;
        st[v] = 1;
        for (int i = h[v]; i != -1; i = ne[i]) 
            if (dist[e[i]] > dist[v] + w[i])
            {
                dist[e[i]] = dist[v] + w[i];
                heap.push({dist[e[i]], e[i]});
            }
    }


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

int main() {
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    while (m --) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    int t = dijkstra();
    printf("%d", t);

    return 0;
}

3.Bellman-Ford算法(存在负权边,有边数限制最短路)

有负权回路,最短路不一定存在

for k 次

​ for 所有边 a, b, w

​ 松弛操作:dist[b] =min(dist[b,dist[a]+w)

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数

请你求出从 1号点到 n 号点的最多经过 k 条边的最短距离,如果无法从 1 号点走到 n 号点,输出 impossible

注意:图中可能 存在负权回路

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

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

struct edge {
    int a, b, w;
} edges[10010];

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 i = 0; i < m; i ++) {
            int a = edges[i].a, b = edges[i].b, w = edges[i].w;
            dist[b] = min(dist[b], w + backup[a]);
        }
    }
    
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < m; i ++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edges[i] = {a, b, c};
    }
    bellman_ford();
    if (dist[n] > 0x3f3f3f3f / 2)   puts("impossible");
    else    printf("%d", dist[n]);

    return 0;
}

4.SPFA算法(与负权边,无负权回路)

给定一个 n个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数

请你求出 1号点到 n 号点的最短距离,如果无法从 11 号点走到 n 号点,则输出 impossible

数据保证不存在负权回路。

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

using namespace std;

const int N = 1e5 + 10;

int idx, h[N], ne[N], e[N], w[N];

int n, m;

// 判断该点是否在队列
bool st[N];
int dist[N];

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

int spfa() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<int> q;
    q.emplace(1);
    st[1] = 1;
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        st[t] = 0;
        for (int i = h[t]; i != -1; i = ne[i]) {
            if (dist[e[i]] > dist[t] + w[i]) {
                dist[e[i]] = dist[t] + w[i];
                if (!st[e[i]]) {
                    q.emplace(e[i]);
                    st[e[i]] = 1;
                }
            }
        }
    }
    return dist[n];
}

int main() {
    ios::sync_with_stdio(false);
    memset(h, -1, sizeof h);
    cin >> n >> m;
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }
    int t = spfa();
    if (t == 0x3f3f3f3f)    cout << "impossible" << endl;
    else    cout << t;

    return 0;

}

5.Floyd求在求最短路(多源)

给定一个 n 个点 m条边的有向图,图中可能存在重边和自环,边权可能为负数。

再给定 k 个询问,每个询问包含两个整数 x 和 y,表示查询从点 x 到点 y 的最短距离,如果路径不存在,则输出 impossible

数据保证图中不存在负权回路。文章来源地址https://www.toymoban.com/news/detail-623806.html

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

using namespace std;

const int N = 210, inf = 1e9;

int d[N][N];

int n;

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] = min(d[i][j], d[i][k] + d[k][j]);
    }
}

int main() {
    int m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
            if (i == j)     d[i][j] = 0;
            else    d[i][j] = inf;
        }
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        d[a][b] = min(d[a][b], c);
    }
    floyd();
    while (k--) {
        int a, b;
        cin >> a >> b;
        if (d[a][b] > inf / 2)      puts("impossible");
        else    cout << d[a][b]<<endl;
    }

    return 0;
}

到了这里,关于图论--最短路问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • python 经典算法之--最短路径算法(Shortest Path Algorithm)

    最短路径算法是一类算法,用于寻找图中两个节点之间的最短路径。最短路径算法可分为单源最短路径算法和多源最短路径算法。单源最短路径算法求解的是一个源点到其它所有节点的最短路径,多源最短路径算法求解的是任意两个节点之间的最短路径。在本次回答中,我们

    2024年02月04日
    浏览(38)
  • 图论——最短路算法

    如上图,已知图G。 问节点1到节点3的最短距离。 可心算而出为d[1,2]+d[2,3]=1+1=2,比d[1,3]要小。 是一种基于三角形不等式的多源最短路径算法。边权可以为负数 表现为a[i,j]+a[j,k]a[i,k]。 算法思想: 枚举“中转站”(k),“起点”(i),“终点”(j) 设d[i,j]为由i点到j点的最短路径 则  初

    2024年02月13日
    浏览(39)
  • 【图论】最短路算法

    不能处理边权为负的情况, 复杂度O(nlogn) 步骤与基本思路 (1)初始化距离数组dist[N],将其所有值赋为0x3f,并将起点1的dist初始化为0,存入优先队列heap中 (2)从所有 未被遍历 的点中找到与起点1的 距离dist[i]最小 的点,并将该点标记为已遍历 (3)利用刚刚遍历的这个点

    2024年02月16日
    浏览(39)
  • 图论(二)之最短路问题

    栗题 https://www.acwing.com/problem/content/851/ https://www.acwing.com/problem/content/852/ 思想 迪杰斯特拉算法采用的是一种贪心的策略。 求源点到其余各点的最短距离步骤如下: 用一个 dist 数组保存源点到其余各个节点的距离,dist[i] 表示源点到节点 i 的距离。初始时,dist 数组的各个元素

    2024年04月13日
    浏览(38)
  • 【图论】单源最短路问题

    Dijkstra算法是一种单源最短路径算法,用于找出图中从一个源点到其他所有点的最短路径。该算法的原理是采用贪心策略,每次将距离源点最近的点加入到已确定最短路径的集合中,并更新其它节点的距离。具体实现过程如下: 初始化距离数组dist[],源点距离为0,其余点距离

    2024年02月13日
    浏览(40)
  • 【图论】最短路的传送问题

    P4568 [JLOI2011] 飞行路线 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 可知背景就是求最短路问题,但难点是可以使一条路距离缩短至0,那如何更好的利用这个机会呢? 此时我们可以用到分层图,如下: 即我们可以免费往下传一次,其实也就相当于两点距离为0了,这时终点应该

    2024年02月12日
    浏览(36)
  • 图论--最短路问题

    邻接表-链式前向星 1.拓扑排序 给定一个 n 个点 m 条边的有向图,点的编号是 11 到 n,图中可能存在重边和自环。 请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出 −1−1。 若一个由图中所有点构成的序列 A 满足:对于图中的每条边 (x,y),x在 A中都出现在

    2024年02月14日
    浏览(36)
  • 图论---最短路径问题

            解决图论问题中的最短路径问题一般有四种算法,分别是Floyd算法、Dijkstra算法、Bellman-Ford算法和SPFA算法,下面介绍一下这几种算法的模板和原理用途。 Floyd算法 原理:Floyd本质上是一个 动态规划 的思想,每一次循环更新 经过前k个节点,i到j的最短路径 。 用途

    2024年02月08日
    浏览(26)
  • 图论 <最短路问题>模板

    有向图 1.邻接矩阵,稠密图 2.邻接表 (常用)单链表,每一个点都有一个单链表 ,插入一般在头的地方插, 图的邻接表的存储方式 树的深度优先遍历 特殊的深度优先搜索,难点是如何实现,一条道走到黑 树的宽度优先遍历 例题:图的层序搜索 拓扑序列(有向图) 例题

    2024年02月14日
    浏览(27)
  • 图论---最短路问题

    单源最短路 n: 点的数量 m: 边的数量 所有边权都是正数 (1)朴素Dijkstra算法 O(n^2) (2)堆优化版的Dijkstra算法 O(mlogn) 存在负权边 (1)Bellmax-Fold O(nm) (让选择不超过k条边的时候使用) (2)SPFA 一般O(m),最坏O(nm) 多源汇最短路 Floyd算法 O(n^3) 每次找到距离起点最近的点,然后用这个点去更新

    2024年02月05日
    浏览(30)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包