最短路（dijkstra、堆优化dijkstra、bellman-ford、spfa、floyd）

在求最短路问题时，不区分有向图和无向图，有向图和无向图的问题都可以用有向图的算法解决，只是存图时有所不同

一、朴素dijkstra算法（基于贪心）(邻接矩阵)（单源最短路、边权为正）(适用于稠密图)（稠密图的m和n^2同级别，稀疏图的m和n同级别）

      时间复杂度O(n^2)

//重复n-1次，每次在剩下的未确定最短距离的点中，找距离源点最近的点，用这个距离来更新每个点到源点的距离
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )  //n-1次
    {
        int t = -1;  //每次找到当前第一个未确定最短距离的点j，用j更新t，以这个t为基准，继续寻找比它距离源点更小的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))   //更新条件
                t = j;  //最终找到当前未确定最短距离的点中距离源点最短的点

        for (int j = 1; j <= n; j ++ )  //用找到的点的距离更新所有点的距离（三角不等式）
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

 二、堆优化版的dijkstra(单源最短路、边权为正)

        时间复杂度O(mlogn)

#include 
#include 
#include 
#include 

using namespace std;

typedef pair<int, int> PII; //pair存点距离源点的距离和该节点的编号

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, greater> heap;//目的是用来找当前未确定最短距离且距离源点最近的点
    heap.push({0, 1});

    while (heap.size())
    {
        auto t = heap.top();//这里的t就是pair类型
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;//编号为ver的点在之前就已经考虑过了，不考虑冗余备份，跳过即可
        st[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];//更新
                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;
}

三、bellman-ford算法(单源最短路、存在负权边) （可以判断是否存在负环，但时间复杂度太高，一般不用它来判断）

       时间复杂度O(nm)

//有边数限制的题目就只能用bellman-ford来做,不能用spfa了，例题如下：

#include 
#include 
#include 

using namespace std;

const int N = 510, M = 10010;

struct Edge
{
    int a, b, c;
}edges[M];//结构体存储边的信息

int n, m, k;
int dist[N];
int last[N];//备份

void bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);

    dist[1] = 0;
    for (int i = 0; i < k; i ++ )   //边数限制，不超过k条边
    {
        memcpy(last, dist, sizeof dist);//防止最后串联，若串联就没法保证边数限制了。因此每次迭代前备份一下，保证只用上一次迭代的结果，这样就不会串联了，从而保证在边数限制内
        //memcpy的效率很高

        for (int j = 0; j < m; j ++ )//遍历了所有边
        {
            auto e = edges[j];
            dist[e.b] = min(dist[e.b], last[e.a] + e.c);
        }
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);

    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edges[i] = {a, b, c};
    }

    bellman_ford();

    if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");//存在负权边。比如说0x3f3f3f3f经过一条值为-2负权边后，后面的点是可以把前面的点更新的。所以这里是dist[n]>0x3f3f3f3f/2,而不是dist[n]==0x3f3f3f3f
    else printf("%d\n", dist[n]);

    return 0;
}

四、spfa算法(单源最短路、存在负权边) (求最短路、判断是否存在负环)（dijkstra可以过的题很多时候spfa也可以过）(spfa也可以做正权图的题)

       时间复杂度 一般情况O(m)   最坏情况O(nm)

#include 
#include 
#include 
#include 

using namespace std;

const int N = 100010;

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 spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;

    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])//对bellman-ford算法进行优化，只将被更新后的点放入队列，用它去更新别人
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    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 == 0x3f3f3f3f) puts("impossible");
    else printf("%d\n", t);

    return 0;
}

题目：判断是否存在负环
#include 
#include 
#include 
#include 

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

五、floyd算法（求任意两点间的最短距离）

       时间复杂度O(n^3)

#include 
#include 
#include 

using namespace std;

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

    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;

    while (m -- )
    {
        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);

        int t = d[a][b];
        if (t > INF / 2) puts("impossible");
        else printf("%d\n", t);
    }

    return 0;
}

 做题的时候不知道为什么，oj上写0x3f会wa，但是写999999999就可以过。