最短路难点不在于证明，在于建图，把一个问题抽象成图，如何定义边，如何定义图

Dijkstra迪杰斯特拉

本质，是不断刷新起点与其他各个顶点之间的 “距离表”。

1. 初始化距离
   一号结点的距离为零，其他结点的距离设为无穷大（看具体的题）。
2. 循环n次，每一次将集合S之外距离最短X的点加入到S中去（这里的距离最短指的是距离1号点最近。点X的路径一定最短，基于贪心，严格证明待看）。然后用点X更新X邻接点的距离。

int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist); //初始化，一开始都是无限大
    dist[1] = 0; //初始化

    for (int i = 0; i < n - 1; i ++ ) // 循环n-1次，每个号都遍历一次(除了最后一个n)
    {
        int t = -1; // 在还未确定最短路的点中，寻找距离最小的点
        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]);  // 用t更新其他点的最短距离
        
        st[t] = true; //进行标记，下次不取这个号
    }

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

堆优化版Dijkstra(适合稀疏图)

堆优化版的dijkstra是对朴素版dijkstra进行了优化，在朴素版dijkstra中时间复杂度最高的寻找距离最短的点O(n^2)可以使用最小堆优化。

1. 一号点的距离初始化为零，其他点初始化成无穷大。
2. 将一号点放入堆中。

3. 不断循环，直到堆空。每一次循环中执行的操作为：
   弹出堆顶（与朴素版diijkstra找到S外距离最短的点相同，并标记该点的最短路径已经确定）。
   用该点更新临界点的距离，若更新成功就加入到堆中。

typedef pair<int, int> PII;

int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定

// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});      // first存储距离，second存储节点编号

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

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

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }

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

bellman - ford

用结构体储存，方便遍历所有边。

bellman-ford算法关注的是快速遍历每一条边，邻接表是以点出发，这些点关联了那些边，如果点非常多，边非常少的话，用邻接表遍历到每一条边就麻烦了，且性能差，不如直接记录边的结构体来的快

int n, m;       // n表示点数，m表示边数
int dist[N];        // dist[x]存储1到x的最短路距离

struct Edge     // 边，a表示出点，b表示入点，w表示边的权重
{
    int a, b, w;
}edges[M];

// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for (int i = 0; i < n; i ++ ) //一共走n步数
    {
        for (int j = 0; j < m; j ++ )
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > dist[a] + w)
                dist[b] = dist[a] + w;
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}

SPFA算法

bellman-ford算法很傻，在该算法中，我们需要遍历很多次所有的边，在遍历的过程中，只有满足dist[b] > dist[a] + w这个条件，距离才会发生改变。SPFA算法进行了改进，只有dist[a]发生变化，才遍历和他相关的边。

Bellman_ford算法会遍历所有的边，但是有很多的边遍历了其实没有什么意义，我们只用遍历那些到源点距离变小的点所连接的边即可，只有当一个点的前驱结点更新了，该节点才会得到更新；因此考虑到这一点，我们将创建一个队列每一次加入距离被更新的结点。

int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储每个点到1号点的最短距离
bool st[N];     // 存储每个点是否在队列中

// 求1号点到n号点的最短路距离
int spfa()
{
    memset(dist, 0x3f, sizeof dist);//初始化很重要
    dist[1] = 0;//不要忘记初始化

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

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

        st[t] = false;//出队后记得恢复

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            //这里判断dist[j]是否发生变化，变化了才可以入队，不能用min
            if (dist[j] > dist[t] + w[i]) 
            {
                dist[j] = dist[t] + w[i];
                //只有j的距离变化了，才可以入队，故不可写在外面
                if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return dist[n];
}

SPFA判断负环

就是在原有的spfa模板上加个cnt[N]用来记录每个点的边数

如果这个边数超过n个，那么一定存在负环

int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N], cnt[N];
// dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N];     // 存储每个点是否在队列中

// 如果存在负环，则返回true，否则返回false。
bool spfa()
{
	// 不需要初始化dist数组
	// 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点
    //由抽屉原理一定有两个点相同，所以存在环。

    queue<int> q;
    for (int i = 1; i <= n; i ++ )
    {
        q.push(i);
        //这里要把所有的点入队，可能有单个的负环
        st[i] = true;
    }

    while (q.size())
    {
        auto 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;
  // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
                if (cnt[j] >= n) return true;   
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

spfa、bellman-ford和djikstra三者的区别

首先，三者都是用来求最短路，但是思想和复杂度不相同。

bellman-ford 和spfa的区别

1.Bellman-ford算法中，循环n次，每次遍历m条边，每次遍历的时候，把入度的点的距离更新成最小。

然而，这样就循环遍历了很多用不到的边。比如第一次遍历，只有第一个点的临边是有效的。

2.因此，spfa算法中，采用邻接表的方式，只用到有效的点（更新了临边的点），直到每个点都是最短距离为止。采用队列优化的方式存储每次更新了的点，每条边最多遍历一次。如果存在负权回路，从起点1出发，回到1距离会变小， 会一直在三个点中循环。

Question:

不用队列，遍历所有的点可以吗？

Ans:

似乎不行，因为是更新了点之后，这个点的临边才可以用，如果没有更新到循环的点，那么循环的点也是不可用的。

spfa和dijkstra的区别：

st用来检验队列中是否有重复的点

spfa从队列中使用了当前的点，会把该点pop掉，状态数组st[i] = false(说明堆中不存在了) ，更新临边之后，把临边放入队列中， 并且设置状态数组为true，表示放入队列中 。如果当前的点距离变小，可能会再次进入队列，因此可以检验负环：

每次更新可以记录一次，如果记录的次数 > n,代表存在负环（环一定是负的，因为只有负环才会不断循环下去）。

st是一个集合，不是检验队列中的点。

dijkstra使用当前点更新临边之后，把该点加入到一个集合中，使用该点更新临边，并把临边节点和距离起点的距离置入堆中（不设置状态数组）。下一次从堆中取最小值，并把对应的节点放入集合中，继续更新临边节点，直到所有的点都存入集合中。因此dijkstra不判断负环。

从上述描述中能看出，dijkstra存放节点的堆，具有单调性，而spfa的队列不需要具有单调性。

Floyd算法

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

初始化：
    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;

// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
    //从i出发，只经过k，到达j的距离
    
    //以k为中继点，k是阶段
    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]);
}

总结