四种最短路总结：

n表示点，m表示边

$Dijkstra-朴素-O(n^2)—适用于稠密图-正权边$

1. 利用邻接矩阵：g[a][b]

2. 初始化数组：d[N] = INF(0x3f3f3f3f), d[1] = 0。

3. 外层循环：遍历数组n-1次（1点的d[1]我们不需计算），每次大循环都会更新一次所有点的d[x]

4. 内层循环1：定义一个序列外的点t，每次循环都会为t点找到更小的d[t]，直到d[t]最小

5. 内层循环2：在d[t]最小的情况下，更新所有点的d[x]，然后进行下一轮大循环

$Dijkstra-堆优化-O(mlogn)—适用于稀疏图-正权边$

1. 利用邻接表 e[], ne[], h[], idx；优先队列priority_queue<PII, vector<PII> ,greater<PII>> heap

2. heap.first储存距离，heap.second储存点

3. 初始化：d[] = INF(0x3f3f3f3f), h[] = -1, d[1] = 0

4. 每次循环取出heap.top()，更新点的距离即可

$Bellman-Ford-O(n*m)-负权边+限制次数搜索$

1. 初始化：struct Edge{int a,b,c} Edge[M]; d[] = INF(0x3f3f3f3f)

2. 注意备份数组backup[]，d[b] = min(d[b], backup[a] + c)防止发生串联更新。

3. k次搜索，遍历m次边

$spfa-O(m)$~$O(n * m)-负权边+正权边+判断负环$

1. 邻接表

2. 初始化：queue<int>q, d[] = INF(0x3f3f3f3f), h[] = -1, d[1] = 0, st[1] = true

3. 每次弹出队头，遍历更新d[x]：if(d[j] > d[t] + w[i]) { d[j] = d[t] + w[i]; if(!st[j]) { q.push(j); st[j] = true; } }

4. 判断负环：

bool spfa()
{
    queue<int> q;

    for (int i = 1; i <= n; i ++ )
    {
        q.push(i);
        st[i] = 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(d[j] > d[t] + w[i])
            {
                d[j] = d[t] + w[i];
                <!--printf("d[%d] = %d\n", j, d[j]);-->
                cnt[j] = cnt[t] + 1;    //如果从1号点到x的最短路中包含至少n个点（自己除外），说明存在环
                <!--printf("cnt[%d] = %d\n", j ,cnt[j]);-->
                if(cnt[j] >= n) return true;

                if(!st[j])
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }

    return false;
}

$Floyd-O(n^3)-多源汇最短路+正权边+负权边（不能有负权回路）$

1. 领接矩阵

2. 初始化：d[]

3. 用k,i,j遍历更新