最短路算法摘要：

最短路算法摘要：

几种算法(n 是点， m是边)：

1.单源最短：：(全部边权为正)朴素Dijkstra 复杂度n^2 （邻接矩阵存， 稠密图） 堆优化Djikstra mLogn （稀疏图， 邻接表）

(存在负权) bellman-ford SPFA（较为常用 ）spfa的一大特色是可以找负环， 当然我目前还没见过笔试考这么难的，打比赛的需要掌握 mn

2.多源最短：：floyd n^3 (可以找到恰好经过k条边的最短路， 倍增法) 也可以找最小环

一道很好的题目，我使用了三种不同的写法，大家一定要每种都熟练掌握。

先来搞定下两种存储方式：

邻接表：其实就是静态链表，h是链表的脑袋，e是该节点， ne是下一节点，w是这个点到下一点的边, idx 是序号

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

邻接矩阵：比较简单就是二维数组

int w[a][b]; // 点a到点b的权是w[a][b]

Dijkstra

必须掌握的基础算法， 基于贪心得来。

堆优化版本大家自己搜。不写了。

const int N = 110, M = 6010, INF = 0x3f3f3f3f;
int w[N][N];
int dist[N];
int n, k;
bool st[N];
class Solution {
public:
    void dijkstra()
    {
        memset(dist, INF, sizeof dist); //注意初始化dist到一个大数，我们才可以用较小值更新
        memset(st, false, sizeof st);
        dist[k] = 0;
       for (int p = 1; p <= n; p++) {
            // 每次找到「最短距离最小」且「未被更新」的点 t
            int t = -1;
            for (int i = 1; i <= n; i++) {
                if (!st[i] && (t == -1 || dist[i] < dist[t])) t = i;
            }
            // 标记点 t 为已更新
            st[t] = true;
            // 用点 t 的「最小距离」更新其他点
            for (int i = 1; i <= n; i++) {
                dist[i] = min(dist[i], dist[t] + w[t][i]);
            }
        }
    }
    int networkDelayTime(vector<vector<int>>& times, int _n, int _k) {
        n = _n, k = _k;
        for (int i = 1; i <= n; i ++)
        {
            for (int j = 1; j <= n; j ++)
            {
                if (i == j) w[i][j] = 0;
                else w[i][j] = INF;
            }
        }

        for (auto e:times)
        {
            int a = e[0], b = e[1], c = e[2];
            w[a][b] = c;
        }
        
        dijkstra();
        int res = 0;
        for (int i = 1; i <= n; i ++)
        {
            res = max(res , dist[i]);
            
        }
        if (res == INF) return -1;
        return res;
    }
};

Spfa

大家邻接表和邻接矩阵的存储方式都需要掌握，本做法用邻接表。

const int N = 110, M = 6010, INF = 0x3f3f3f3f;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
bool st[N];



class Solution {
public:


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

    void spfa(int start) { //无需初始化st是因为spfa结束条件就是所有节点出队列
        queue<int> q;
        q.push(start);
        memset(dist, 0x3f, sizeof dist);
        dist[start] = 0;
        while (q.size()) {
            int t = q.front();
            q.pop();
            st[t] = false;
            for (int i = h[t]; ~i; 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;
                    }
                }
            }
        }
    }


    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        memset(h, -1, sizeof h);
        idx = 0;
        for (auto& e: times) {
            int a = e[0], b = e[1], c = e[2];
            add(a, b, c);
        }
        spfa(k);
        int res = 1;
        for (int i = 1; i <= n; i ++ ) res = max(res, dist[i]);
        if (res == INF) res = -1;
        return res;


    }
};

Floyd

复杂度比较高，但是本题数据小，我最爱的无脑算法

const int N = 110, M = 6010, INF = 0x3f3f3f3f;
int w[N][N];
int n, k;

class Solution {
public:
    void floyd()
    {
        for (int k = 1; k <= n; k ++)  //k是中转站，其实flyod本质是一种dp的思想，也就是我们得到的最短路一定是靠一个最短中转站得来
        {
            for (int i = 1; i <= n; i ++)
            {
                for (int j = 1; j <= n; j ++)
                {
                    w[i][j] = min(w[i][j], w[i][k] + w[k][j]);
                }
            }
        }
    }

    
    int networkDelayTime(vector<vector<int>>& times, int _n, int _k) {
        n = _n, k = _k;
        for (int i = 1; i <= n; i ++)
        {
            for (int j = 1; j <= n; j ++)
            {
                if (i == j) w[i][j] = 0;
                else w[i][j] = INF;
            }
        }

        for (auto e:times)
        {
            int a = e[0], b = e[1], c = e[2];
            w[a][b] = c;
        }

        floyd();
        int res = 0;
        for (int i = 1; i <= n; i ++)
        {
            res = max(res , w[k][i]);
        }
        if (res == INF) return -1;
        else return res;
    }
};