朴素版Dijkstra

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

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist); // 初始化距离为正无穷
    dist[1] = 0; // 源点距离初始化为0

    // 为啥要循环n - 1次呢？
    // 因为每进行一次第三步就能在未被标记的点集中找到距离源点最近的点
    // 总共有n个点, 出去第一个点还剩下n -1个点。因此需要循环n - 1次。
    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1; // 与源点距离没有确定的点中找到距离最近的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;  

        // 标记最短距离已经被确定
        st[t] = true;

        // 以最近的点更新其他所有点
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);
    }

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

缺点：
1. 每次在未被标记的点集中找距离最小的值时间复杂度很高
2. 不必更新那些与距离最小的点没有边的点，只需更新临边就可以了

优化方法：
1. 堆优化找最小值
2. 利用宽搜的思想求解

对比可含负权边的Bellman-ford算法：

朴素Dijkstra算法与Bellman-ford算法的区别：
1. 朴素Dijkstra是考虑的更新点，关注点总的距离最短，Bellman-ford考虑的是边，每次利用三角不等式更新，关注点在每一条边。
2. 朴素Dijkstra算法每次迭代需要找到距离源点最近的节点，而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 ++ )
    {
        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];
}

对比最小生成树问题中Prim算法：

朴素Dijkstra算法与Prim算法的区别：
1. dist数组含义不同，Dijkstra表示与源点的最短距离，Prim表示与集合的最短距离
2. st数组含义不同：Dijkstra表示该点与源点的最短距离是否确定，Prim表示该点与连通集合的最短距离是否确定，也意味着是否在集合中
3. 循环次数不同：Dijkstra 循环n-1次， Prim循环n次

int n;      // n表示点数
int g[N][N];        // 邻接矩阵，存储所有边
int dist[N];        // 存储其他点到当前最小生成树的距离
bool st[N];     // 存储每个点是否已经在生成树中

// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{
    memset(dist, 0x3f, sizeof dist); // 边初始化为无穷大

    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        int t = -1; // 找到距离集合最近的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j; 

        // 标记距离集合最近的点已经被找到，加入到集合中
        st[t] = true;

        if (i && dist[t] == INF) return INF;

        if (i) res += dist[t];

        // 更新其他点到新集合的距离
        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

堆优化版Dijkstra

typedef pair<int, int> PII;

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

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});
    st[1] = true;

    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];
            // 为什么不是把所有临边push到队列中呢？
            // 因为如果没有更新就意味着不是正无穷，说明已经入队了
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j}); //把所有更新后的边push到队列中去
            }
        }



    }

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

对比宽搜模板：

堆优化的Dijkstra算法与宽搜的区别：
1. 宽搜中的队列换成优先队列
2. 出队的点更新相邻的点到源点的距离
3. 入队条件为原则上为所有临边入队，但是这样会导致重复入队。原因就是未被更新意味着值肯定不是无穷大，说明已入队

queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

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

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!s[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

对比可含负权边的spfa算法：

堆优化的Dijkstra算法与spfa算法区别：
1. st数组的含义不同：Dijkstra算法中表示该节点与源点的最短路径是否确定，出队就已经确定了，st[ver] = true;
而spfa算法中的st数组表示该点是否在队列中，如果不在并且更新了，就需要入队。这保证了入队的肯定是被更新过的
2. 算法原理不同：Dijkstra算法是贪心，逐步找离源点最近的节点，并以该节点更新其他节点。而spfa算法是只要有被更新的节点，就要以该节点更新其他点，从源点开始

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

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])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return dist[n];
}

多元最短路径：

Floyd

初始化：
    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()
{
    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]);
}

最小生成树

Kruskal

int n, m;       // n是点数，m是边数
int p[N];       // 并查集的父节点数组

struct Edge     // 存储边
{
    int a, b, w;

    bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
}edges[M];

int find(int x)     // 并查集核心操作
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal()
{
    sort(edges, edges + m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);
        if (a != b)
        {
            p[a] = b;
            res += w;
            cnt ++ ;
        }
    }

}