最短路和最小生成树（注意事项以及代码分析）

1 Dijkstra(求最短路)

1.1 Dijkstra具体过程

1：进行n次迭代每次迭代中，找出未确认最短路的点。
2: 通过这个点对其他点进行松弛操作。并将该带标记为
   最短路。

1.2 Dijkstra代码(朴素版本 邻接矩阵)

Dijkstra题目链接

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

using namespace std;

typedef pair<int, int> PII;
typedef long long ll;
int const INF = 0x3f3f3f3f;
//-------------------------------------------------------
int const N = 510;
int n, m;
int map[N][N],dist[N];
bool book[N];
//-------------------------------------------------------
void init()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == j) map[i][j] = 0;
            else map[i][j] = INF;
        }
    }
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 1; i <= n; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++)
            if ((t == -1 || dist[t] > dist[j]) && !book[j]) t = j;

        for (int j = 1; j <= n; j++)
            dist[j] = min(dist[j], dist[t] + map[t][j]);

        book[t] = true;
    }
    if (dist[n] != INF) return dist[n];
    return -1;
}

//-------------------------------------------------------
int main()
{
    cin >> n >> m;
    init();
    for (int i = 1; i <= m; i++)
    {
        int a, b, len; cin >> a >> b >> len;
        map[a][b] = min(map[a][b], len);
    }
    int ans = dijkstra();
    cout << ans << endl;
}
//-------------------------------------------------------
/*

*/

1.3 Dijkstra代码(堆优化版本 邻接表)

Dijkstra题目链接

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

using namespace std;

typedef pair<int, int> PII;
typedef long long ll;
int const INF = 0x3f3f3f3f;
//-------------------------------------------------------
int const N = 3e5 + 10;
int n, m;
int h[N], ne[N], e[N], w[N], dist[N], idx;
bool book[N];
//-------------------------------------------------------

void init()
{
    memset(h, -1, sizeof h);
    idx = 0;
}

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

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);                    
    dist[1] = 0;                                    //初始化dist数组
    priority_queue<PII,vector<PII>,greater<PII>> que;//定义大根堆维护dist数组
    que.push({ 0,1 });                              //fistr 表示距离 second 表示点
    while (!que.empty())
    {
        PII t = que.top(); que.pop();
        int ver = t.second;
        if (book[ver] == true) continue;
        book[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                que.push({ dist[j],j });
            }
        }
    }
    if (dist[n] == INF) return -1;
    return dist[n];
}
//-------------------------------------------------------
int main()
{
    init();                                         //初始化 h[]
    cin >> n >> m; 
    for (int i = 1; i <= m; i++)
    {
        int a, b, len; cin >> a >> b >> len;
        add(a, b, len);
    }
    int ans = dijkstra();
    cout << ans << endl;
}
//-------------------------------------------------------

/*

*/

1.4 Dijkstra总结

图的存储方式

1.邻接矩阵（稠密图）：

    在初始化的过程中如果存在重边将最短的存入图中

2.邻接表（稀疏图）：

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

    void init()
    {
        idx = 0;
        memset(h, -1, sizeof h);
    }

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

Dijkstra 细节问题

1. Dijkstra 适用于权值不为负的。
2. 在Dijkstra的堆优化中，first必须是距离只有这样，堆才会按照距离排序

2 spfa bellman-ford（求最短路）

2.1 bellman-ford

1. 将边用结构体存储，通过权值进行排序。
2. 通过n-1次迭代更新dist[]数组求出最短路（其中n-1是边数限制，如果n次之后还存在边更新说明有负环）

2.2 bellman-ford 代码

bellman-ford

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

using namespace std;

typedef pair<int, int> PII;
typedef long long ll;
int const INF = 0x3f3f3f3f;
//-------------------------------------------------------
int const N = 1e4 + 10;
int n, m, k;
int dist[N], backup[N];
struct edge
{
    int a, b, len;
}e[N];
//-------------------------------------------------------
int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++)
        cin >> e[i].a >> e[i].b >> e[i].len;
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 1; i <= k; i++)
    {
        memcpy(backup, dist, sizeof dist);
        for (int j = 1; j <= m; j++)
        {
            int a = e[j].a;
            int b = e[j].b;
            int len = e[j].len;
            dist[b] = min(dist[b], backup[a] + len);
        }
    }
    if (dist[n] > INF / 2) cout << "impossible" << endl;
    else cout << dist[n] << endl;
}
//-------------------------------------------------------

/*

*/

2.3 bellman-ford注意事项

1. 通过backup数组防止发生串联
2. 由于途中存在权值为负的边，并且在更行时所有边都会便利到，所以无法到达的距离可能小于INF
3. 当k>=n dist仍然变化说明存在负环

2.4 spfa

1. 相当于bellman-ford的优化，由于dist[b]要改变必须存在dist[a]变小。
2. 开一个对联存储改变的dist[a]
3. 一直循环直到队列位0

2.5 spfa 代码

spfa

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

using namespace std;

typedef pair<int, int> PII;
typedef long long ll;
int const INF = 0x3f3f3f3f;
//-------------------------------------------------------
int const N = 1e5 + 10;
int n, m;
int h[N], ne[N], w[N], e[N], dist[N], idx;
bool book[N];

void init()
{
    memset(dist, 0x3f, sizeof dist);
    memset(h, -1, sizeof h);
    idx = 0;
}

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

int spfa()
{
    dist[1] = 0;
    queue<int> que;
    que.push(1);
    while (!que.empty())
    {
        int t = que.front(); que.pop();
        book[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];
                if (!book[j])
                {
                    book[j] = true;
                    que.push(j);
                }
            }
        }
    }
    return dist[n];
}

//-------------------------------------------------------
int main()
{
    init();
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b, len; cin >> a >> b >> len;
        add(a, b, len);
    }
    int ans = spfa();
    if (ans == INF) cout << "impossible" << endl;
    else cout << ans << endl;

}
//-------------------------------------------------------

/*

*/

2.6 spfa判断负环

1. 通过维护一个cnt[],判断起点到当前点走过的边数，如果边数大于等于n说明存在负环。
2. queue<> 初始载入所有点

spfa判断负环

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

using namespace std;

typedef pair<int, int> PII;
typedef long long ll;
int const INF = 0x3f3f3f3f;
//-------------------------------------------------------
int const N = 1e5 + 10;
int n, m;
int h[N], ne[N], w[N], e[N], dist[N], cnt[N], idx;
bool book[N];

void init()
{
    memset(dist, 0x3f, sizeof dist);
    memset(h, -1, sizeof h);
    idx = 0;
}

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

bool spfa()
{
    dist[1] = 0;
    queue<int> que;
    for (int i = 1; i <= n; i++) que.push(i);
    while (!que.empty())
    {
        int t = que.front(); que.pop();
        book[t] = false;
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                cnt[j]++;
                if (cnt[j] >= n) return true;
                dist[j] = dist[t] + w[i];
                if (book[j]==false)
                {
                    book[j] = true;
                    que.push(j);
                }
            }
        }
    }
    return false;
}

//-------------------------------------------------------
int main()
{
    init();
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b, len; cin >> a >> b >> len;
        add(a, b, len);
    }
    if (spfa()) cout << "Yes" << endl;
    else cout << "No" << endl;
}
//-------------------------------------------------------

/*

*/

2.7 spfa注意事项

1. spfa是由bellman-ford优化而来的时间复杂度远小于O（nm）。
2. spfa不需要backup是由于bellman—ford的上一题是有边数限制的最短路防止串联，而spfa单纯就是求最短路所以不需要考虑串联。
3. spfa无穷远不会更新位小于INF由于dist[b]的前驱一定是更新过的，才会进行与后继最短路求解，所以INF与INF的比较是不会进行的，因此负权无法更新无穷大。

3 Floyd

3.1 Floyd求最短路

1. 动态规划，三重循环，松弛操作

3.2 Floyd代码

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

using namespace std;

typedef pair<int, int> PII;
typedef long long ll;
int const INF = 0x3f3f3f3f;
//-------------------------------------------------------
int const N = 210;
int map[N][N];
int n, m, t;

void init()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i == j) map[i][j] = 0;
            else map[i][j] = INF;
}

//-------------------------------------------------------
int main()
{
    cin >> n >> m >> t;
    init();
    for (int i = 1; i <= m; i++)
    {
        int a, b, len; cin >> a >> b >> len;
        map[a][b] = min(map[a][b], len);
    }

    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                map[i][j] = min(map[i][j], map[i][k] + map[k][j]);

    while (t--)
    {
        int a, b; cin >> a >> b;
        if (map[a][b] >= INF / 2) cout << "impossible" << endl;
        else cout << map[a][b] << endl;
    }
}
//-------------------------------------------------------

/*

*/

3 prim Kruskal最小生成树

3.1 prim算法

1. 进行n次迭代，每次找到距离集合最近且未标记过的点，res+=dist[t]。
2. 用t更新其他点

3.2 prim 代码

prim

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

using namespace std;

typedef pair<int, int> PII;
typedef long long ll;
int const INF = 0x3f3f3f3f;
//-------------------------------------------------------
int const N = 510;
int map[N][N],dist[N];
int n, m;
bool book[N];

void init()
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == j) map[i][j] = 0;
            else map[i][j] = INF;
        }
    }
}

int prim()
{
    int res = 0;
    memset(dist, 0x3f, sizeof dist);
    for (int i = 1; i <= n; i++)
    {
        int t = -1;
        for (int j = 1; j <= n; j++)
            if ((t == -1 || dist[t] > dist[j]) && !book[j]) t = j;

        if (i != 1 && dist[t] == INF) return INF;
        if (i != 1) res += dist[t];

        for (int j = 1; j <= n; j++)
            dist[j] = min(dist[j], map[t][j]);

        book[t] = true;
    }
    return res;
}

//-------------------------------------------------------
int main()
{
    cin >> n >> m;
    init();
    for (int i = 1; i <= m; i++)
    {
        int a, b, len; cin >> a >> b >> len;
        map[a][b] = map[b][a] = min(map[a][b], len);
    }
    int ans = prim();
    if (ans == INF) cout << "impossible" << endl;
    else cout << ans << endl;
}
//-------------------------------------------------------

/*

*/

3.3 Kruskal

1. 将所有边排序
2. 从小到达枚举如果不连通就联通一下

3.4 Kruskal 代码

Kruskal

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

using namespace std;

typedef pair<int, int> PII;
typedef long long ll;
int const INF = 0x3f3f3f3f;
//-------------------------------------------------------
int const N = 1e5 + 10, M = 2e5 + 10;
int p[N];
struct edge
{
    int a, b, len;
}e[M];

bool cmp(edge a, edge b)
{
    return a.len < b.len;
}

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
//-------------------------------------------------------
int main()
{
    int n, m; cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b, len; cin >> a >> b >> len;
        e[i] = { a,b,len };
    }

    sort(e + 1, e + 1 + m, cmp);
    for (int i = 1; i <= n; i++) p[i] = i;

    int ans = 0; int cnt = 0;
    for (int i = 1; i <= m; i++)
    {
        int a = e[i].a;
        int b = e[i].b;
        int len = e[i].len;
        a = find(a);
        b = find(b);
        if (a != b)
        {
            cnt++;
            ans += len;
            p[a] = b;
        }
    }
    if (cnt < n - 1) cout << "impossible" << endl;
    else cout << ans << endl;
}
//-------------------------------------------------------

/*

*/