首页 > 其他分享 >AcWing854. Floyd求最短路

AcWing854. Floyd求最短路

时间:2024-08-30 13:53:17浏览次数:15  
标签:int 短路 迪杰 算法 Floyd 斯特拉 顶点 AcWing854 负权

在这里插入图片描述

注意:Floyd是求图里面任意两个点x,y之间的最短距离

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

using namespace std;

const int N = 210, INF = 1e9;

int n, m, Q;
int d[N][N];

void floyd()
{
//枚举1~k个中间节点,尝试通过这几个点中转来达到更短距离
    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()
{
    scanf("%d%d%d", &n, &m, &Q);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;//自己到自己是0距离
            else d[i][j] = INF;//

    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        //min是因为处理重边,c是权重
        d[a][b] = min(d[a][b], c);
    }

    floyd();

    while (Q -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);

        int t = d[a][b];
        //如果存在负权环,会走该分支,会一直减小总路径
        //或者真的是不可达也会走该分支
        if (t > INF / 2) puts("impossible");
        //可达的情况
        else printf("%d\n", t);
    }

    return 0;
}


扩展内容:

迪杰斯特拉和弗洛伊德算法区别:

迪杰斯特拉(Dijkstra)算法和弗洛伊德(Floyd-Warshall)算法都是图论中用于求解最短路径问题的著名算法,但它们在设计、应用场景和效率上有所不同:

  1. 算法设计

    • 迪杰斯特拉算法:是一种贪心算法,用于在加权图中找到单个源点到所有其他顶点的最短路径。它适用于没有负权边的图。
    • 弗洛伊德算法:是一种动态规划算法,用于在加权图中找到所有顶点对之间的最短路径。它可以处理包含负权边的图,但不能处理负权环。
  2. 应用场景

    • 迪杰斯特拉算法:适用于单源最短路径问题,例如从某个城市到其他所有城市的最短路线。
    • 弗洛伊德算法:适用于全局最短路径问题,例如在所有城市之间找到最短的路线。
  3. 效率

    • 迪杰斯特拉算法:时间复杂度为 O ( V 2 ) O(V^2) O(V2)(使用简单的数组实现)或 O ( ( V + E ) log ⁡ V ) O((V+E) \log V) O((V+E)logV)(使用优先队列实现),其中 V V V 是顶点数, E E E 是边数。
    • 弗洛伊德算法:时间复杂度为 O ( V 3 ) O(V^3) O(V3),其中 V V V 是顶点数。对于大型图,这可能比迪杰斯特拉算法慢。
  4. 处理负权边

    • 迪杰斯特拉算法:不能正确处理包含负权边的图,因为负权边可能导致算法无法正确更新最短路径。
    • 弗洛伊德算法:可以处理负权边,但必须确保图中没有负权环,否则算法无法找到正确的最短路径。
  5. 数据结构

    • 迪杰斯特拉算法:通常使用优先队列(如最小堆)来选择下一个最近的顶点。
    • 弗洛伊德算法:通常使用二维数组来存储所有顶点对之间的最短路径信息。
  6. 初始化

    • 迪杰斯特拉算法:需要初始化源点到所有其他顶点的距离,源点到自己的距离为0,到其他顶点的距离为无穷大。
    • 弗洛伊德算法:需要初始化一个 V × V V \times V V×V 的距离矩阵,其中对角线元素为0,其他元素为边的权重或无穷大(如果顶点间没有直接的边)。

总结来说,选择哪种算法取决于具体问题的需求,如果需要找到单个源点到所有其他顶点的最短路径,且图中没有负权边,迪杰斯特拉算法是更好的选择。如果需要找到所有顶点对之间的最短路径,或者图中可能存在负权边,弗洛伊德算法可能更适合。

标签:int,短路,迪杰,算法,Floyd,斯特拉,顶点,AcWing854,负权
From: https://blog.csdn.net/weixin_46028606/article/details/141612747

相关文章

  • 求两点间最短路的Dijkstra算法及其matlab程序详解
    #################本文为学习《图论算法及其MATLAB实现》的学习笔记#################设源点为u0u_{0}u0​,目标......
  • C++实现的最短路径问题
    最短路径问题最短路径问题是图论中的一个经典问题,旨在寻找从一个起点到一个终点的最短路径。最常见的算法包括Dijkstra算法、Bellman-Ford算法和Floyd-Warshall算法。这些算法被广泛用于导航系统、网络路由等领域。问题描述输入:一个加权图,表示图中各节点之间的连接和权......
  • Bellmanford与Spfa解决存在负边权的单源汇最短路问题
    上个文章讲了Dijkstra算法但是Dijkstra算法只能解决单源汇非负边权的最短路问题这次文章来讲单源汇存在负边权的解决方法Bellmanforda和spfa算法二者适用场景区别:一般来说使用spfa就能解决大部分的问题,但问题出现不超过k条边的时候应当使用Bellmanford算法BellmanFord:随意存......
  • 相遇(容斥+最短路+分类,水紫)
    第5题   相遇 查看测评数据信息给定一个有n个节点m条边的无向图,在某一时刻节点st上有一个动点a,节点end上有一个动点b,动点a向节点end方向移动,要求是尽快到达end点,与此同时,动点b向节点st方向移动,要求是尽快到达st点,但是整个过程中a和b不能相遇,问两点不相遇一共有多少种......
  • 回顾图存储与最短路算法
    图的存储与最短路问题一、图的储存1.邻接矩阵邻接矩阵使用二维vecto......
  • 最短路
    这是仙人掌的模板题,仙人掌不能有自环,但是可以有重边。多颗仙人掌组成的图叫做沙漠。将仙人掌的每个环缩成一个点之后,就会形成树仙人掌转树要利用圆方树:①.任选一个点为根②.此时每个环有且仅有唯一一个点到根的距离最近。然后将环中的点分类,离根节点最近的点叫“头”,剩余的点作......
  • Dijkstra、Bellman_Ford、SPFA、Floyd算法复杂度比较
    说明Dijkstra:适用于权值为非负的图的单源最短路径,用斐波那契堆的复杂度O(E+VlgV)BellmanFord:适用于权值有负值的图的单源最短路径,并且能够检测负圈,复杂度O(VE)SPFA:适用于权值有负值,且没有负圈的图的单源最短路径,论文中的复杂度O(kE),k为每个节点进入Queue的次数,且k一般<=2,但此处......
  • 最短路 - Dijkstra 算法
    Dijkstra(迪杰斯特拉)算法是基于贪心思想的单源最短路算法暴力Dijkstra具体如下:structnode{ intv,w;};vector<node>e[N];intdist[N],vis[N];e[u]存的是节点u的所有出边的终点和边权,dist[u]存u到原点s的最小距离,vis[u]标记是否走过voiddijkstra(int......
  • 《数据结构》最短路径Dijkstra算法
                                    最短路径Dijkstra算法分析生长点ABCDEFP(A)=FAD(A)=130P(B)=FBD(B)=24P(C)=FCD(C)=10P(D)=——D(D)=无穷P(E)=——D(E)=无穷CP(A)=FAD(A......
  • 最短路算法
    1.Dijkstra算法算法思想:\(dijkstra\)算法采用的是贪心的思想。(1)定义一个\(dis\)数组,\(dis[i]\)表示i点到源点的最短路径,设源点的\(dis\)值为0,其他\(dis\)值为\(∞\)。(2)选出其中的最小\(dis\)值,进行标记并更新它相邻的\(dis\)值。(3)不断循环操作(2)。优点:dijkstra算......