简易版最短路, 最小生成树

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

简易版最短路, 最小生成树

作者：

迷弟 , 2021-04-03 09:51:41 , 所有人可见 , 阅读 445

已补全
2021.04.06 图论多建图（多做题，每题适配模板，思考为什么可以这样，做多了就通过大量实践理解）

Dijkstra-朴素O(n^2)

初始化距离数组, dist[1] = 0, dist[i] = inf;

for n次循环每次循环确定一个min加入S集合中，n次之后就得出所有的最短距离

将不在S中dist_min的点->t

t->S加入最短路集合

用t更新到其他点的距离

Dijkstra-堆优化O(mlogm)

利用邻接表，优先队列

在priority_queue<PII, vector<PII>, greater<PII> > heap;中将返回堆顶

利用堆顶来更新其他点，并加入堆中类似宽搜

Bellman_fordO(nm)

注意连锁想象需要备份, struct Edge{inta,b,c} Edge[M];

初始化dist, 松弛dist[x.b] = min(dist[x.b], backup[x.a]+x.w);

松弛k次，每次访问m条边

Spfa O(n)~O(nm)

利用队列优化仅加入修改过的地方

for k次

for 所有边利用宽搜模型去优化bellman_ford算法

更新队列中当前点的所有出边

Floyd O(n^3)

初始化d

k, i, j 去更新d

①最短路 - 正权

Dijkstra
// 集合 S = { a, b, c…} 当前已经确定最短路径的点【】
// ① dist[1] = 0; 起点距离设为0. 其他所有点距离dist[i] = 设定+无穷
// ② for i : n 循环n次
// 找到t 为不在s当中的距离最近的点
// t放进s中
// 用t更新其他点的距离 1 – t – x. dist[x] > dist[t] + w
// 看从1经过t达到x的距离，是否比1不经t直接到x的距离。小的话，就更新x的距离(和路径)。
// 每次循环(iteration迭代)都可以确定一个点到起点的最短距离

const int N = 511;

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

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < n; i ++ )
    {
        int t = -1; //一开始初始化为-1。【t存储当前访问的点】
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dist[t] > dist[j])) 
            //如果是未确定最短距离的点，以及t是初始值或t距离大于j （当前t不是最短的，j是）
            //【寻找还未确定最短路的点中路径最短的点】
                t = j; //t选为路径更短的点j. 直到遍历完所有点。
            //t即是与1号点距离最短的点。

        //把t加入s集合中
        st[t] = true; 
        //然后再用这个点去更新剩余点到该点的距离(相邻的点路径值)
        for (int j = 1; j <= n; j++)
            dist[j] = min(dist[j], dist[t] + g[t][j]); //用1--t--x来更新1---x的长度
    }
    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); //最短的重边即可
    }
    int res = dijkstra();
    printf("%d", res);
    return 0;
}

堆优化：

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

using namespace std;

const int N = 1e6 + 10;

typedef pair<int, int> PII;

int n, m;
int h[N], e[N], w[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; //定义起点路径距离为0

    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1}); //一①号点，距离是0，编号是1
    while (heap.size()) //当堆不是空时
    {
        //      每次取出当前最小的点      //
        auto t = heap.top(); //找到当前距离最小的点 //小根堆，堆顶即是
        heap.pop();
        int ver = t.second, distance = t.first; //ver表示当前点的编号
        if (st[ver]) continue; //如果已经出现过，则这个点是冗余备份，直接跳过即可
        st[ver] = true;
        // （一共m次）
        for (int i = h[ver]; i != -1; i = ne[i]) //注意邻接表的含义。h[ver]以ver编号为起点的相邻的节点链，i不是-1即没到尾节点，就走到下一个点
        {
            int j = e[i]; //当前值
            if (dist[j] > distance + w[i]) //如果当前距离大于经过t到i的距离的话，就更新(选经过t的这条更短的路)
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], 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); //邻接表添加边
    }
    int t = dijkstra();
    printf("%d\n", t);
    return 0;
}

单源
多源
存在负边权

$$ \large最短路问题 \begin {cases} 单源最短路 \begin {cases} 所有边权为正数 \begin {cases} 朴素Dijkstra算法O(n^2)\\\ 堆优化Dijkstra算法O(mlogn) \end {cases} \\\ 存在负边权 \begin {cases} BellmanFord算法O(mn)\\\ SPFA算法O(m)–最坏O(mn) \end {cases} \end{cases}\\\ \\\ 多源最短路：Floyd算法O(n^3) \end {cases} $$

Dijkstra 原理：贪心，【t是距离最近的那个点，如果他能被选，就是最短路(反证法)】每次找经过t到x点距离最小的那个。如果路径经过t到x的距离小于其他直接到x的距离，则把经过t的这条路径更新为当前路径。

②Bellman_Ford (cht打错名字的算法)

也是玩dist[], 每次取min(dist[a] + w)即可（用backup[a]来避免串连更新）

const int N = 510, M = 10010;

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

struct Edge //结构体随便存一下边，一会儿循环时用, i ---m
{
    int a, b, w;
}edges[M];

int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist); //原理①初始化为+无穷，第一个点为0
    dist[1] = 0;
    for (int i = 0; i < k; i ++ )
    {
        memcpy(backup, dist, sizeof dist); //每次迭代前需将数组备份一遍 （解决串连情况，不会一次循环把a, b, c...都改了）//【每次只用上一次迭代结果】
        for (int j = 0; j < m; j++)
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            dist[b] = min(dist[b], backup[a] + w); //只用上一次迭代结果更新当前结果(数)
        }
    }
    if (dist[n] > 0x3f3f3f / 2) return -1; //由于算法设计限制，正无穷只是用0x3f表示，所以可能出现倒数第二个点 一个负数-1，把最后一个点更新为0x3f - 1 （判断不出来到不了情况了）.所以用0x3f除2即可。
    return dist[n];
}


int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < m; i++)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        edges[i] = {a, b, w};
    }
    int t = bellman_ford();
    if (t == -1) puts("impossible"); //t = -1则最短路不存在
    else printf("%d\n" , t);

    return 0;
}

③SPFA

单源最短路带负权

const int N = 100010;

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

void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    queue<int> q; //队列来存储所有待更新的点
    q.push(1);
    st[1] = true; // st[i] 数组存当前点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]; //如果j比t+w大，则更新为更小的路径
                if (!st[j]) { //如果j不在队列中，才把它加入队中
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    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);
    }
    int t = spfa();
    if (t == -1) puts("impossible");
    else printf("%d\n", t);
    return 0;
}

判断负环：

const int N = 100010;

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

void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int 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]; //如果j比t+w大，则更新为更小的路径
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;
                if (!st[j]) { //如果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);
    }
    int t = spfa();
    if (spfa()) puts("Yes");
    else puts("No");
    return 0;
}

④多源最短路 Floyd

const int N = 210, INF = 1e9;

int n, m, Q;
int 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()
{
    scanf("%d%d%d", &n, &m, &Q); //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;
        } //任意两点距离初始化为正无穷，除了i到i本身为0

    while(m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c); //c = weight 权重
        d[a][b] = min(d[a][b], c); 
    }
    floyd();
    //询问Q
    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]);
    }
}

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

using namespace std;

const int N = 210, INF = 1e9;
int n, m, Q;
int d[N][N]; //lin jie ju zhen

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]);
            //DP:从i到j，只经过...k个点最短距离=min(从i到k，只经过1...k-1个点最短距离+从k到j，只经过1...k-1个点的最短距离)
}

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; //自环此题(最短路)不用考虑 0即可
            else d[i][j] = INF; // 所有边初始化 ---> 正无穷
        }
    floyd();
    while (m --) //m条边
    {
        int a, b, w;
        cin >> a >> b >> w;
        d[a][b] = min(d[a][b], w);
    }

    while (Q --)
    {
        int a, b;
        cin >> a >> b;
        if (d[a][b] > INF / 2) puts("impossible");
        else printf("%d\n", d[a][b]);
    }
    return 0;
}

最小生成树
普通图(稠密)Prim
稀疏图Kruskal

2 评论

迷弟 2021-04-04 16:32

$$
\large最短路问题 
\begin {cases} 
单源最短路 
\begin {cases}  
    所有边权为正数
    \begin {cases}  
        朴素Dijkstra算法O(n^2)\\\
        堆优化Dijkstra算法O(mlogn)
    \end {cases} \\\
    存在负边权
    \begin {cases}  
        BellmanFord算法O(mn)\\\
        SPFAO(m)--最坏O(mn)
    \end {cases}
\end{cases}\\\
\\\ 
多源最短路 ：Floyd算法O(n^3)
\end {cases}
$$

苟三 2021-04-04 10:36

大佬好，能请问一下您的这个图是怎么用Markdown画出来的嘛？

App 内打开