最短路问题 - 模板总结(Dijkstra + Bellman-Ford + SPFA + Floyd)_njuptACMcxk的博客-程序员宅基地

技术标签: 算法  最短路  dijkstra  acm竞赛  spfa  数据结构  

最短路问题 - 模板总结(Dijkstra + Bellman-ford + SPFA + Floyd)

最短路问题分类图:
在这里插入图片描述

1、Dijkstra算法(正边权单源最短路问题)

1-1、朴素Dijkstra算法-O(n2)

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


分析:

本 题 m > n 2 , 用 O ( n 2 ) 算 法 更 优 。 本题m>n^2,用O(n^2)算法更优。 m>n2O(n2)

稠 密 图 用 邻 接 矩 阵 存 储 。 注 意 到 有 重 边 , 在 读 入 的 时 候 取 重 边 中 最 小 的 权 重 即 可 。 稠密图用邻接矩阵存储。注意到有重边,在读入的时候取重边中最小的权重即可。

具体落实:

① 、 整 个 点 集 分 为 两 部 分 , 一 部 分 是 到 起 点 的 最 短 距 离 已 经 确 定 , 记 为 S 1 。 另 一 部 分 未 确 定 , 记 为 S 2 。 首 先 初 始 化 距 离 d i s 数 组 为 + ∞ , 起 点 所 在 位 置 d i s [ S ] = 0 , 就 说 将 起 点 加 入 S 1 。 再 用 起 点 去 更 新 S 2 中 的 点 j 到 起 点 的 最 短 距 离 d i s [ j ] 。 接 下 来 的 每 次 操 作 , 都 从 S 2 中 选 择 一 个 到 S 1 距 离 最 近 的 点 t , 再 用 点 t 去 更 新 S 2 中 的 点 到 起 点 的 最 短 距 离 。 ①、整个点集分为两部分,一部分是到起点的最短距离已经确定,记为S_1。另一部分未确定,记为S_2。\\\qquad首先初始化距离dis数组为+∞,起点所在位置dis[S]=0,就说将起点加入S_1。\\\qquad再用起点去更新S_2中的点j到起点的最短距离dis[j]。\\\qquad接下来的每次操作,都从S_2中选择一个到S_1距离最近的点t,再用点t去更新S_2中的点到起点的最短距离。 S1S2dis+dis[S]=0S1S2jdis[j]S2S1ttS2

② 、 以 上 操 作 重 复 n 次 , 将 n 个 点 都 加 入 到 S 1 中 , 此 时 的 d i s 数 组 存 储 的 就 是 到 任 意 点 到 起 点 的 最 短 距 离 。 ②、以上操作重复n次,将n个点都加入到S_1中,此时的dis数组存储的就是到任意点到起点的最短距离。 nnS1dis
模板:

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

using namespace std;

const int N=510;

int n,m,g[N][N],dis[N];
bool st[N];

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

int main()
{
    
    memset(g,0x3f,sizeof g);
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
    
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=min(g[a][b],c);
    }
    
    cout<<dijkstra(1)<<endl;
    
    return 0;
}

1-2、堆优化的Dijkstra算法-O(mlogn)

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

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

输入格式
第一行包含整数n和m。

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

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

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

数据范围
1≤n,m≤1.5×105,
图中涉及边长均不小于0,且不超过10000。

输入样例:
3 3
1 2 2
2 3 1
1 3 4
输出样例:
3

分析:

n < = 1 0 5 , 此 时 O ( n 2 ) 效 率 明 显 低 于 O ( m l o g 2 n ) , 采 用 堆 优 化 版 的 D i j k s t r a 算 法 。 n<=10^5,此时O(n^2)效率明显低于O(mlog_2n),采用堆优化版的Dijkstra算法。 n<=105O(n2)O(mlog2n)Dijkstra

稀 疏 图 , 采 用 邻 接 表 存 储 图 。 稀疏图,采用邻接表存储图。

通 过 分 析 朴 素 的 D i j k s t r a 算 法 , 容 易 发 现 , 我 们 每 一 趟 都 需 要 遍 历 点 集 中 的 所 有 点 来 寻 找 到 当 前 到 原 点 距 离 最 近 的 点 。 事 实 上 , 这 个 过 程 可 以 通 过 小 根 堆 来 维 护 。 通过分析朴素的Dijkstra算法,容易发现,\\我们每一趟都需要遍历点集中的所有点来寻找到当前到原点距离最近的点。\\事实上,这个过程可以通过小根堆来维护。 Dijkstra

这 样 我 们 每 次 从 小 根 堆 中 取 出 的 就 是 S 2 中 到 起 点 距 离 最 近 的 点 , 再 用 该 点 更 新 S 2 中 与 其 相 邻 的 点 到 起 点 的 距 离 , 并 加 入 堆 中 。 再 重 复 操 作 即 可 。 这样我们每次从小根堆中取出的就是S_2中到起点距离最近的点,再用该点更新S_2中与其相邻的点到起点的距离,\\并加入堆中。再重复操作即可。 S2S2

代码:

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

#define P pair<int,int>

using namespace std;

const int N=1e6+10;

int n,m,e[N],w[N],ne[N],h[N],idx;
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()
{
    
    int dis[N];
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    
    priority_queue<P,vector<P>,greater<P>> heap;
    heap.push({
    0,1});
    
    while(heap.size())
    {
    
        P t=heap.top();
        heap.pop();
        
        int id=t.second;
        if(st[id]) continue;
        st[id]=true;
        
        for(int i=h[id];~i;i=ne[i])
        {
    
            int j=e[i];
            if(dis[j]>dis[id]+w[i])
            {
    
                dis[j]=dis[id]+w[i];
                heap.push({
    dis[j],j});
            }
        }
    }
    
    return dis[n]==0x3f3f3f3f ? -1 : dis[n];
    
}


int main()
{
    
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
    
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    
    cout<<dijkstra()<<endl;
    
    return 0;
}

2、Bellman-Ford算法(带负权且经过的边的数量有限制)-O(nm)

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

分析:

有 负 权 回 路 , 最 短 路 未 必 存 在 ( 起 点 到 终 点 的 路 径 上 未 经 过 负 权 环 , 此 时 仍 然 是 有 最 短 路 的 ) 。 有负权回路,最短路未必存在(起点到终点的路径上未经过负权环,此时仍然是有最短路的)。 ()

共 迭 代 k 次 , 每 次 遍 历 所 有 的 边 , 更 新 所 有 点 到 起 点 的 最 短 距 离 。 共迭代k次,每次遍历所有的边,更新所有点到起点的最短距离。 k

代码:

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

using namespace std;

const int N=10010;

int n,m,k,backup[N];
struct Edge
{
    
    int u,v,w;  
}e[N];

int bellman_ford()
{
    
    int dis[N];
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    
    for(int i=0;i<k;i++)
    {
    
        memcpy(backup,dis,sizeof dis);
        for(int j=1;j<=m;j++)
        {
    
            int a=e[j].u,b=e[j].v,w=e[j].w;
            dis[b]=min(dis[b],backup[a]+w);
        }
    }
    
    return dis[n]>0x3f3f3f3f/2 ? -1 : dis[n];
}

int main()
{
    
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    
    int t=bellman_ford();
    if(t==-1) puts("impossible");
    else cout<<t<<endl;
    
    return 0;
}

3、SPFA算法(带负权的最短路)-O(m)~O(nm)

3-1、SPFA求最短路

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

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

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

输入格式
第一行包含整数n和m。

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

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

如果路径不存在,则输出”impossible”。

数据范围
1≤n,m≤105
图中涉及边长绝对值均不超过10000。

输入样例:
3 3
1 2 5
2 3 -3
1 3 4
输出样例:
2

分析:

S P F A 算 法 是 B e l l m a n − F o r d 算 法 的 优 化 , 我 们 发 现 B F 算 法 每 次 迭 代 均 要 遍 历 所 有 的 边 , 但 事 实 上 , 并 不 是 所 有 边 均 会 被 更 新 得 更 小 。 转 移 方 程 : d i s [ b ] = m i n ( d i s [ b ] , d i s [ a ] + w ) , 可 见 , 只 有 当 d i s [ a ] 减 小 , d i s [ w ] 才 会 变 小 。 因 此 , 只 有 当 某 个 点 到 起 点 的 距 离 变 小 , 经 过 该 节 点 的 其 他 点 到 起 点 的 距 离 才 可 能 变 小 。 SPFA算法是Bellman-Ford算法的优化,\\我们发现BF算法每次迭代均要遍历所有的边,但事实上,并不是所有边均会被更新得更小。\\转移方程:dis[b]=min(dis[b],dis[a]+w),可见,只有当dis[a]减小,dis[w]才会变小。\\因此,只有当某个点到起点的距离变小,经过该节点的其他点到起点的距离才可能变小。 SPFABellmanFordBFdis[b]=min(dis[b],dis[a]+w)dis[a]dis[w]

我 们 采 用 B F S 的 思 想 来 对 B F 算 法 进 行 优 化 , 用 一 个 队 列 来 存 储 到 起 点 距 离 变 短 的 点 , 每 次 出 队 后 用 该 点 更 新 与 其 相 邻 节 点 到 起 点 的 距 离 , 再 将 更 新 过 的 到 起 点 距 离 变 短 的 点 继 续 入 队 。 我们采用BFS的思想来对BF算法进行优化,\\用一个队列来存储到起点距离变短的点,每次出队后用该点更新与其相邻节点到起点的距离,\\再将更新过的到起点距离变短的点继续入队。 BFSBF

需 要 注 意 , 由 于 存 在 负 权 边 , 因 此 我 们 初 始 化 的 + ∞ 可 能 会 略 微 的 减 小 。 因 此 我 们 认 为 若 某 点 到 起 点 的 距 离 大 于 + ∞ 2 , 则 说 明 从 起 点 无 法 到 达 该 点 。 需要注意,由于存在负权边,因此我们初始化的+∞可能会略微的减小。\\因此我们认为若某点到起点的距离大于\frac{+∞}{2},则说明从起点无法到达该点。 +2+

代码:

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

using namespace std;

const int N=100010;

int n,m,e[N],h[N],w[N],ne[N],idx;
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 spfa()
{
    
    int dis[N];
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    
    queue<int> Q;
    Q.push(1);
    st[1]=true;
    
    while(Q.size())
    {
    
        int u=Q.front();
        Q.pop();
        st[u]=false;
        
        for(int i=h[u];~i;i=ne[i])
        {
    
            int j=e[i];
            if(dis[j]>dis[u]+w[i])
            {
    
                dis[j]=dis[u]+w[i];
                if(!st[j])
                {
    
                    st[j]=true;
                    Q.push(j);
                }
            }
        }
    }
    
    return dis[n];
}

int main()
{
    
    memset(h,-1,sizeof h);
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
    
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    
    int t=spfa();
    if(t==0x3f3f3f3f) puts("impossible");
    else cout<<t<<endl;
    
    return 0;
}

3-2、SPFA判断负环

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


分析:

与 求 最 短 路 的 思 路 类 似 , 需 额 外 增 加 数 组 c n t [ x ] , 记 录 起 点 到 x 点 经 过 的 边 数 。 与求最短路的思路类似,需额外增加数组cnt[x],记录起点到x点经过的边数。 cnt[x]x

若 c n t [ x ] > = n , 表 示 从 起 点 到 x 点 经 过 了 n 条 边 , 意 味 着 经 过 了 n + 1 个 点 , 由 抽 屉 原 理 , 必 然 有 某 个 点 经 过 了 2 次 。 这 就 说 明 了 图 中 存 在 一 个 负 环 。 若cnt[x]>=n,表示从起点到x点经过了n条边,意味着经过了n+1个点,由抽屉原理,必然有某个点经过了2次。\\这就说明了图中存在一个负环。 cnt[x]>=nxnn+12

与 最 短 路 不 同 的 是 , 这 次 我 们 要 先 将 所 有 点 入 队 。 因 为 负 环 可 能 从 某 个 起 点 出 发 未 必 能 经 过 , 需 要 将 所 有 点 都 当 作 起 点 跑 S P F A 。 与最短路不同的是,这次我们要先将所有点入队。\\因为负环可能从某个起点出发未必能经过,需要将所有点都当作起点跑SPFA。 SPFA

代码:

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

using namespace std;

const int N = 2010, M = 10010;

int n, m;
int h[N], w[M], e[M], ne[M], idx;
int dist[N], cnt[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 ++ ;
}

bool spfa()
{
    
    queue<int> q;

    for (int i = 1; i <= n; i ++ )
    {
    
        st[i] = true;
        q.push(i);
    }

    while (q.size())
    {
    
        int t = q.front();
        q.pop();

        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 true;
                if (!st[j])
                {
    
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

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);
    }

    if (spfa()) puts("Yes");
    else puts("No");

    return 0;
}



4、Floyd(多源最短路)-O(n3)

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

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

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

输入格式
第一行包含三个整数n,m,k

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

接下来k行,每行包含两个整数x,y,表示询问点x到点y的最短距离。

输出格式
共k行,每行输出一个整数,表示询问的结果,若询问两点间不存在路径,则输出“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
1

思 路 十 分 简 单 , 枚 举 中 间 点 k , 更 新 所 有 从 i 到 j 且 经 过 k 的 路 径 的 最 短 距 离 。 思路十分简单,枚举中间点k,更新所有从i到j且经过k的路径的最短距离。 kijk

同 样 的 , 由 于 存 在 负 权 边 , 若 距 离 仍 大 于 + ∞ 2 , 则 认 为 两 点 之 间 不 连 通 。 同样的,由于存在负权边,若距离仍大于\frac{+∞}{2},则认为两点之间不连通。 2+

代码:

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

#define inf 0x3f3f3f3f

using namespace std;

const int N=210;

int n,m,q,d[N][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()
{
    
    cin>>n>>m>>q;
    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;
            
    for(int i=0;i<m;i++)
    {
    
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        d[a][b]=min(d[a][b],c);
    }
    
    floyd();
    
    while(q--)
    {
    
        int a,b;
        scanf("%d%d",&a,&b);
        if(d[a][b]>inf/2) puts("impossible");
        else printf("%d\n",d[a][b]);
    }
    
    return 0;
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/njuptACMcxk/article/details/105780629

智能推荐

Floyd-Warshall、Dijkstra、Bellman–Ford、SPFA

Floyd-Warshall(弗洛伊德算法) 弗洛伊德算法的原理是动态规划,用于计算两点之间的最短路径。该算法的优点在于极其简单,代码仅几行。缺点是时间复杂度高O(n3),空间复杂度Ω(n2) 算法描述 算法用于比较图结构中两...

最短路问题 - dijkstra算法、Bellman_Ford算法、SPFA模板、Floyd算法

寻找最短路径指的是找出从图中...1:单源最短路:给定一个源结点,求出这个点到其他所有点的最短路径,有Dijkstra和Bellman-ford两种算法,Dijkstra只能求解所有边权都为正的情况,Bellman-ford可以求解边权为正或...

最短路问题 - 模板总结(Dijkstra + Bellman-Ford + SPFA + Floyd)

文章目录最短路问题 - 模板总结(Dijkstra + Bellman-ford + SPFA + Floyd)1、Dijkstra算法(正边权单源最短路问题)1-1、朴素Dijkstra算法-O(n^2^)1-2、堆优化的Dijkstra算法-O(mlogn)2、Bellman-ford算法...

最短路(Dijkstra,Bellman-Ford,SPFA,Floyd算法)

寒假学了最短路算法,半懂不懂的,玩了一个假期以后彻底忘的干干净净; 考完蓝桥杯,我要重新捡起最短路,不能再堕落了!!! 这里是我一边学一边整理的自以为比较全的最短路合集了QwQ! 最短路 一、单源最短路 1....

最短路算法汇总(Dijkstra,Bellman-Ford,SPFA以及Floyd)

1)Dijkstra 算法 ---求单源最短路径(边的权值非负),所谓 ...2) Bellman-Ford 算法--- 求单源最短路径(边的权值允许为负值,但不存在负权值回路); Dijkstra算法:顶点的dist值一经确定就不会改变,而Bellman...

图的最短路 Bellman-Ford Dijkstra Floyd_Warshall SPFA Johnson 图文分析

强行把自己从小说的...文章目录单源最短路问题1(Bellman-Ford算法)单源最短路问题2(Dijkstra算法) 最短路问题是给定两个顶点,在以这两个点为起点和终点的路径中,求边的权值和最小的的路径。 单源最短路是...

hdu-2544-最短路-(bellman-ford、dijkstra、floyd、SPFA算法)

最短路问题在程序竞赛中是经常出现的内容,解决单源最短路经问题的有bellman-ford和dijkstra两种算法,其中,dijikstra算法是对bellman的改进。同时介绍了floyd算法、SPFA算法。   题目传送门:...

最短路知识点总结(Dijkstra,Floyd,SPFA,Bellman-Ford)

如果采用的实现方法合适,Dijkstra运行时间要低于Bellman-Ford算法。 思路:  如果存在一条从i到j的最短路径(Vi.....Vk,Vj),Vk是Vj前面的一顶点。那么(Vi...Vk)也必定是从i到k的最短路径。为了求出最短路径,...

模板--Floyd Dijkstra Bellman-Ford spfa 四种最短路经典算法

Floyd Dijkstra Bellman-Ford spfa 四种最短路经典算法汇总 最短路 Problem Description在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的...

最短路(floyd\dijkstra\Bellman-Ford\SPFA)

 floyd算法只有五行代码,代码简单,三个for循环就可以解决问题,所以它的时间复杂度为O(n^3),可以求多源最短路问题。 2.思想:  Floyd算法的基本思想如下:从任意节点A到任意节点B的最短路径不外乎2种可能,...

Dijkstra、Bellman-Ford、SPFA、ASP、Floyd-Warshall 算法分析

图论中,用来求最短路的方法有很多,适用范围和时间复杂度也各不相同。 本文主要介绍的算法的代码主要来源如下: Dijkstra: Algorithms(《算法概论》)Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani...

最短路算法-Floyd,dijkstra,bellman-Ford,SPFA

一 Floyd算法 五行算法,遍历遍历遍历,用于所有点对的最短路径,若数据范围小可以使用,时间复杂度 O(N^3),空间复杂度O(N^2); 代码: for(int k=1;k&lt;=n;k++) for(int i=1;i&lt;=n;i++) for(int j=1;j&lt...

最短路算法桶(Dijkstra,Floyd,Bellman-Ford,Spfa)

自己对最短路的简单总结并不涉及详解   1.Dijkstra 算法思想:(求单源最短路,朴素算法复杂度O(n^2),堆优化O(nlogn) 将点分为两类,一类为已被更新最短距离的点为“标记点”,另一类为还没有被更新最短距离的...

五种常见的最短路算法 (朴素Dijkstra,堆优化Dijkstra, Bellman-Ford,SPFA,Floyd)

朴素Dijkstra, 堆优化Dijkstra,Bellman-Ford,SPFA, Floyd。这几种算法有各自的优势和劣势,适用于不同的场景。文章的难度不大,适合算法初学者学习。 五种最短路算法之间的区别 注:n表示图中点的数目,m表示图...

最短路 Dijkstra Floyd Bellman-Ford SPFA模板及例题 (一次性搞定最短路类型的问题)

从城市A到城市B,有时候可以直达也可以途径其他城市到达,怎样选择最短的路径到达就是最短路问题。 分为单源最短路(所有点到某一特定点的最短路径)和多源最短路(任意两点间的最短路径)。根据边的正负也可以分为...

最短路模板Dijkstra Bellman-Ford Floyd SPFA

(做了好久才想起整理模板) 基本最短路算法集锦 ...算法总结: ...①Dijkstra算法用的是贪心策略,每次都找当前...②Bellman-Ford算法是Dijkstra的一种变式,它摒弃了贪心的策略,但是每次都需要松弛所有的路径,所

最短路模板整理(Dijkstra+Bellman-ford+spfa+Floyd)

最短路问题总览 一、单源最短路 1.所有边权都是正数 (1)朴素dijkstra算法 (时间复杂度:O(n^2)) (2)堆优化版dijkstra算法(时间复杂度:O(mlogn)) 2.存在负权边 (1)Bellman-ford算法(时间复杂度:O(nm)...

Acwing算法基础课学习笔记(八)--搜索与图论之最短路问题-Dijkstra&&bellman-ford&&spfa&&Floyd

最短路问题是一个比较大的问题,我们将花一节课的时间来介绍:

最短路径算法对比比较(bellman-ford,dijkstra,spfa,floyd比较)

bellman-ford(贝尔曼夫德算法) spfa 空间复杂度 O(N²) O(M) O(M) O(M) 时间复杂度 O(N³) O((m+n)logN) O(MN) 最坏也是O(NM) 适用情况 稠密图和顶点...

几个最短路径算法Floyd、Dijkstra、Bellman-Ford、SPFA的比较.pdf

几个最短路径算法Floyd、Dijkstra、Bellman-Ford、SPFA的比较.pdf

四种最短路算法 Dijkstra、Bellman-Ford、Spfa、Floyd

常见的最短路问题有哪些? 源点: 起点 汇点: 终点 判断图是什么图:m是 n2n^2n2 级别的话就是稠密图,m是 nnn 级别的就是稀疏图(n是点数,m是边数) 边权: 离散数学或数据结构中,图的每条边上带的一个数值,他...

图的最短路径:Dijkstra、Bellman-Ford、SPFA、Floyd、A*算法汇总

图的表示方法最常用的表示图的方法是邻接矩阵与邻接表。邻接矩阵表示法设G是一个有n(n&gt;0)个顶点的图,V(G)={v1, v2, …, vn},则邻接矩阵AG是一个n阶二维矩阵。在该矩阵中,如果vi至vj有一条边,则(i, j)项的值为1,...

最短路 Dijkstra Floyd Bellman-Ford SPFA模板及例题

从城市A到城市B,有时候可以直达也可以途径其他城市到达,怎样选择最短的路径到达就是最短路问题。 分为单源最短路(所有点到某一特定点的最短路径)和多源最短路(任意两点间的最短路径)。根据边的正负也可以分为...

最短路径算法 模板_Dijkstra_Bellman.ford_Floyd_spfa

1.图的邻接表 模板 邻接表详讲 #include int main() { int u[10],v[10],w[10],first[10],next[10]; int n,m,i,j; scanf("%d%d",&n,&m); for(i=1;i;i++) { first[i] = -1; } for(i=1;i;i++) { scanf("%...

算法基础课—搜索与图论(三)最短路问题——Dijkstra、bellman-ford、spfa、Floyd

@[TOC]算法基础课—搜索与图论(三) 最短路问题——Dijkstra算法、bellman-ford算法、spfa算法、Floyd算法 最短路算法 问题类型 源点——起点,汇点——终点 单源最短路,即起点是固定的,求其到任意点的最短路 ...

随便推点

推荐文章

热门文章

相关标签