头像

Hasity




离线:31分钟前



Hasity
31分钟前



Hasity
12小时前

未优化的代码:

#include<iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 510, M = 100010;

int h[N], e[M], ne[M], w[M], idx;//邻接矩阵存储图
int state[N];//state 记录是否找到了源点到该节点的最短距离
int dist[N];//dist 数组保存源点到其余各个节点的距离
int n, m;//图的节点个数和边数

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

void Dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));//dist 数组的各个元素为无穷大
    dist[1] = 0;//源点到源点的距离为置为 0
    for (int i = 0; i < n; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++)//遍历 dist 数组,找到没有确定最短路径的节点中距离源点最近的点t
        {
            if (!state[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        }

        state[t] = 1;//state[i] 置为 1。

        for (int j = h[t]; j != -1; j = ne[j])//遍历 t 所有可以到达的节点 i
        {
            int i = e[j];
            dist[i] = min(dist[i], dist[t] + w[j]);//更新 dist[j]
        }


    }
}

int main()
{
    memset(h, -1, sizeof(h));//邻接矩阵初始化

    cin >> n >> m;
    while (m--)//读入 m 条边
    {
        int a, b, w;
        cin >> a >> b >> w;
        add(a, b, w);
    }

    Dijkstra();
    if (dist[n] != 0x3f3f3f3f)//如果dist[n]被更新了,则存在路径
        cout << dist[n];
    else
        cout << "-1";
}

优化

看一下算法的时间复杂度:

for(i:1 ~ n)//n次
{
    t <- 没有确定最短路径的节点中距离源点最近的点;//每次遍一遍历dist数组,n次的复杂度是O(n^2)
    state[t] = 1;
    更新 dist;//每次遍历一个节点的出边,n次遍历了所有节点的边,复杂度为O(e)
}

算法的主要耗时的步骤是从dist 数组中选出:没有确定最短路径的节点中距离源点最近的点 t。只是找个最小值而已,没有必要每次遍历一遍dist数组。

在一组数中每次能很快的找到最小值,很容易想到使用小根堆。可以使用库中的小根堆(推荐)或者自己编写。

代码:

#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;//ver:节点编号,distance:源点距离ver 的距离

        if (st[ver]) continue;//如果距离已经确定,则跳过该点
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])//更新ver所指向的节点距离
        {
            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;
}

//参考yxc

使用小根堆后,找到 t 的耗时从 O(n^2) 将为了 O(1)。每次更新 dist 后,需要向堆中插入更新的信息。所以更新dist的时间复杂度有 O(e) 变为了 O(e*logn)。总时间复杂度有 O(n^2) 变为了 O(n + e*longn)。适用于稀疏图。


总结

迪杰斯特拉算法适用于求正权有向图中,源点到其余各个节点的最短路径。注意:图中可以有环,但不能有负权边。

例如:如下图就不能使用迪杰斯特拉算法求节点 1 到其余各个节点的最短距离。
14.png

求个点赞~~




Hasity
12小时前

1




Hasity
12小时前

迪杰斯特拉算法采用的是一种贪心的策略。

求源点到其余各点的最短距离步骤如下:

  1. 用一个 dist 数组保存源点到其余各个节点的距离,dist[i] 表示源点到节点 i 的距离。初始时,dist 数组的各个元素为无穷大。
    用一个状态数组 state 记录是否找到了源点到该节点的最短距离,state[i] 如果为真,则表示找到了源点到节点 i 的最短距离,state[i] 如果为假,则表示源点到节点 i 的最短距离还没有找到。初始时,state 各个元素为假。
    03.png

  2. 源点到源点的距离为 0。即dist[1] = 0。
    04.png

  3. 遍历 dist 数组,找到一个节点,这个节点是:没有确定最短路径的节点中距离源点最近的点。假设该节点编号为 i。此时就找到了源点到该节点的最短距离,state[i] 置为 1。
    05.png

  4. 遍历 i 所有可以到达的节点 j,如果 dist[j] 大于 dist[i] 加上 i -> j 的距离,即 dist[j] > dist[i] + w[i][j](w[i][j] 为 i -> j 的距离) ,则更新 dist[j] = dist[i] + w[i][j]。
    06.png

  5. 重复 3 4 步骤,直到所有节点的状态都被置为 1。
    071.png

  6. 此时 dist 数组中,就保存了源点到其余各个节点的最短距离。
    13.png


伪代码:

int dist[n],state[n];
dist[1] = 0, state[1] = 1;
for(i:1 ~ n)
{
    t <- 没有确定最短路径的节点中距离源点最近的点;
    state[t] = 1;
    更新 dist;
}

#include<iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 510, M = 100010;

int h[N], e[M], ne[M], w[M], idx;//邻接矩阵存储图
int state[N];//state 记录是否找到了源点到该节点的最短距离
int dist[N];//dist 数组保存源点到其余各个节点的距离
int n, m;//图的节点个数和边数

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

void Dijkstra()
{
    memset(dist, 0x3f, sizeof(dist));//dist 数组的各个元素为无穷大
    dist[1] = 0;//源点到源点的距离为置为 0
    for (int i = 0; i < n; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++)//遍历 dist 数组,找到没有确定最短路径的节点中距离源点最近的点t
        {
            if (!state[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        }

        state[t] = 1;//state[i] 置为 1。

        for (int j = h[t]; j != -1; j = ne[j])//遍历 t 所有可以到达的节点 i
        {
            int i = e[j];
            dist[i] = min(dist[i], dist[t] + w[j]);//更新 dist[j]
        }


    }
}

int main()
{
    memset(h, -1, sizeof(h));//邻接矩阵初始化

    cin >> n >> m;
    while (m--)//读入 m 条边
    {
        int a, b, w;
        cin >> a >> b >> w;
        add(a, b, w);
    }

    Dijkstra();
    if (dist[n] != 0x3f3f3f3f)//如果dist[n]被更新了,则存在路径
        cout << dist[n];
    else
        cout << "-1";
}

优化

看一下算法的时间复杂度:

for(i:1 ~ n)//n次
{
    t <- 没有确定最短路径的节点中距离源点最近的点;//每次遍一遍历dist数组,n次的复杂度是O(n^2)
    state[t] = 1;
    更新 dist;//每次遍历一个节点的出边,n次遍历了所有节点的边,复杂度为O(e)
}

算法的主要耗时的步骤是从dist 数组中选出:没有确定最短路径的节点中距离源点最近的点 t。只是找个最小值而已,没有必要每次遍历一遍dist数组。

在一组数中每次能很快的找到最小值,很容易想到使用小根堆。可以使用库中的小根堆(推荐)或者自己编写。

代码:

#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;//ver:节点编号,distance:源点距离ver 的距离

        if (st[ver]) continue;//如果距离已经确定,则跳过该点
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])//更新ver所指向的节点距离
        {
            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;
}

//参考yxc

使用小根堆后,找到 t 的耗时从 O(n^2) 将为了 O(1)。每次更新 dist 后,需要向堆中插入更新的信息。所以更新dist的时间复杂度有 O(e) 变为了 O(e*logn)。总时间复杂度有 O(n^2) 变为了 O(n + e*longn)。适用于稀疏图。


总结

迪杰斯特拉算法适用于求正权有向图中,源点到其余各个节点的最短路径。注意:图中可以有环,但不能有负权边。

例如:如下图就不能使用迪杰斯特拉算法求节点 1 到其余各个节点的最短距离。
14.png

求个点赞~~




Hasity
12小时前

prim 算法干的事情是:给定一个无向图,在图中选择若干条边把图的所有节点连起来。要求边长之和最小。在图论中,叫做求最小生成树。

prim 算法采用的是一种贪心的策略。

每次将离连通部分的最近的点和点对应的边加入的连通部分,连通部分逐渐扩大,最后将整个图连通起来,并且边长之和最小。

我们将图中各个节点用数字 1 ~ n 编号。

05.png

要将所有景点连通起来,并且边长之和最小,步骤如下:

  1. 用一个 state 数组表示节点是否已经连通。state[i] 为真,表示已经连通,state[i] 为假,表示还没有连通。初始时,state 各个元素为假。即所有点还没有连通。
    用一个 dist 数组保存各个点到连通部分的最短距离,dist[i] 表示 i 节点到连通部分的最短距离。初始时,dist 数组的各个元素为无穷大。
    用一个 pre 数组保存节点的是和谁连通的。pre[i] = k 表示节点 i 和节点 k 之间需要有一条边。初始时,pre 的各个元素置为 -1。
    06.png

  2. 从 1 号节点开始扩充连通的部分,所以 1 号节点与连通部分的最短距离为 0,即disti[1] 置为 0。
    07.png

  3. 遍历 dist 数组,找到一个还没有连通起来,但是距离连通部分最近的点,假设该节点的编号是 i。i节点就是下一个应该加入连通部分的节点,stata[i] 置为 1。
    用青色点表示还没有连通起来的点,红色点表示连通起来的点。
    这里青色点中距离最小的是 dist[1],因此 state[1] 置为 1。
    08.png

  4. 遍历所有与 i 相连但没有加入到连通部分的点 j,如果 j 距离连通部分的距离大于 i j 之间的距离,即 dist[j] > w[i][j](w[i][j] 为 i j 节点之间的距离),则更新 dist[j] 为 w[i][j]。这时候表示,j 到连通部分的最短方式是和 i 相连,因此,更新pre[j] = i。
    与节点 1 相连的有 2, 3, 4 号节点。1->2 的距离为 100,小于 dist[2],dist[2] 更新为 100,pre[2] 更新为1。1->4 的距离为 140,小于 dist[4],dist[4] 更新为 140,pre[2] 更新为1。1->3 的距离为 150,小于 dist[3],dist[3] 更新为 150,pre[3] 更新为1。
    09.png

  5. 重复 3 4步骤,直到所有节点的状态都被置为 1.
    这里青色点中距离最小的是 dist[2],因此 state[2] 置为 1。
    10.png
    与节点 2 相连的有 5, 4号节点。2->5 的距离为 80,小于 dist[5],dist[5] 更新为 80,pre[5] 更新为 2。2->4 的距离为 80,小于 dist[4],dist[4] 更新为 80,pre[4] 更新为2。
    11.png
    选dist[4],更新dist[3],dist[5],pre[3],pre[5]。
    12.png13.png
    选dist[5],没有可更新的。
    14.png
    选dist[3],没有可更新的。
    15.png

  6. 此时 dist 数组中保存了各个节点需要修的路长,加起来就是。pre 数组中保存了需要选择的边。
    16.png


伪代码

int dist[n],state[n],pre[n];
dist[1] = 0;
for(i : 1 ~ n)
{
    t <- 没有连通起来,但是距离连通部分最近的点;
    state[t] = 1;
    更新 dist 和 pre;
}

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 510;
int g[N][N];//存储图
int dt[N];//存储各个节点到生成树的距离
int st[N];//节点是否被加入到生成树中
int pre[N];//节点的前去节点
int n, m;//n 个节点,m 条边

void prim()
{
    memset(dt,0x3f, sizeof(dt));//初始化距离数组为一个很大的数(10亿左右)
    int res= 0;
    dt[1] = 0;//从 1 号节点开始生成 
    for(int i = 0; i < n; i++)//每次循环选出一个点加入到生成树
    {
        int t = -1;
        for(int j = 1; j <= n; j++)//每个节点一次判断
        {
            if(!st[j] && (t == -1 || dt[j] < dt[t]))//如果没有在树中,且到树的距离最短,则选择该点
                t = j;
        }

        st[t] = 1;// 选择该点
        res += dt[t];
        for(int i = 1; i <= n; i++)//更新生成树外的点到生成树的距离
        {
            if(dt[i] > g[t][i] && !st[i])//从 t 到节点 i 的距离小于原来距离,则更新。
            {
                dt[i] = g[t][i];//更新距离
                pre[i] = t;//从 t 到 i 的距离更短,i 的前驱变为 t.
            }
        }
    }
}

void getPath()//输出各个边
{
    for(int i = n; i > 1; i--)//n 个节点,所以有 n-1 条边。

    {
        cout << i <<" " << pre[i] << " "<< endl;// i 是节点编号,pre[i] 是 i 节点的前驱节点。他们构成一条边。
    }
}

int main()
{
    memset(g, 0x3f, sizeof(g));//各个点之间的距离初始化成很大的数
    cin >> n >> m;//输入节点数和边数
    while(m --)
    {
        int a, b, w;
        cin >> a >> b >> w;//输出边的两个顶点和权重
        g[a][b] = g[b][a] = min(g[a][b],w);//存储权重
    }

    prim();//求最下生成树
    //getPath();//输出路径
    return 0;
}



优化

上面代码的时间复杂度为 O(n^2)。

与Dijkstra类似,Prim算法也可以用堆优化,优先队列代替堆,优化的Prim算法时间复杂度O(mlogn)。适用于稀疏图,但是稀疏图的时候求最小生成树,Kruskal 算法更加实用。

Dijkstra 算法的优化见:

迪杰斯特拉算法–助我去网吧:https://mp.weixin.qq.com/s/dvxtcGBuVCQ8xH6cy3p0ng

画图不易,求个点赞~~




Hasity
1天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 39. 对称的二叉树

Hasity
1天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



Hasity
1天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 38. 二叉树的镜像

Hasity
1天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 37. 树的子结构

Hasity
1天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~