一.Dijkstra 算法 （单源最短路径）

例题：743. 网络延迟时间

以起点 u 为中心，逐步向外扩展并更新其他顶点的「最短路径」。

「Dijkstra 算法」运用了「贪心思想」，它运行的每一步都是选择当前已知的顶点的「最小权重」去寻找其他顶点的「最短路径」。

用vector vector<pair> 存邻接表，用priority_queue维护下一个最小能更新相邻节点的值，

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<pair<int, int>>> g(n+1); // 邻接表 x表示出节点，g[x].first表示入节点，g[x].second表示出节点
        for (auto& t : times) {
            g[t[0]].emplace_back(t[1], t[2]);
        }
        vector<int> dis(n+1, INT_MAX);
        dis[k] = 0;
        auto cmp =[](const pair<int, int> a,const pair<int, int> b){
            return a<b;
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp); //pair<最短值,当前节点>
        pq.push({0,k});
        while(!pq.empty()){
            auto [dx,x] = pq.top();
            pq.pop();
            if(dx>dis[x]) { //已经出过堆，说明之前有更新过，不用更新了
                continue;
            }
            for(auto &[y,d]:g[x]){
                int new_dis = dx+d;
                if(new_dis<dis[y]){
                    dis[y] = new_dis;
                    pq.emplace(new_dis,y);
                }
            }
        }
        int answer = 0;
        for(int i=1;i<=n;i++){
            answer = max(answer,dis[i]);
        }
        return answer==INT_MAX?-1:answer;
    }
};

二.Kruskal 算法 （最小生成树）

例题：1584. 连接所有点的最小费用 - 力扣（LeetCode）

思路：边排序，每次加入最小边，如果成环则不加入，环的判断用并查集

class UnionFind //并查集
{
    vector<int>root;
    public:
    UnionFind (int n)
    {
        root.resize(n+1);
        for(int i = 1; i <= n ;i++) root[i] = i;
    }
    int find(int x)
    {
        return root[x] == x ? x : root[x] = find(root[x]);
    }
    void merge(int x,int y)
    {
        root[find(x)] = root[find(y)];
    }
    bool isconnect(int x,int y)
    {
        return find(x) == find(y);
    }
};

class Solution {
public://index表示并查集中的点，vector<int>存{instance,i,j};
    int minCostConnectPoints(vector<vector<int>>& points) {
        vector<vector<int>>graph;
        for(int i = 0; i < points.size(); i++)
            for(int j = i + 1; j < points.size(); j++)
            {
                int instance = get_instance(points[i],points[j]);
                graph.push_back({instance,i,j});
            }
        sort(begin(graph),end(graph),[](const auto&a,const auto&b)
        {
            return a.front() < b.front();
        });  
        UnionFind uf(points.size() + 1);
        int cnt = 0,res = 0;
        for(const auto& it : graph)
        {
            if(cnt == points.size() - 1) break;
            if(uf.isconnect(it[1],it[2]))continue;
            else
            {
                uf.merge(it[1],it[2]);
                res += it[0];
                cnt++;
            }
        }
        return res;
    }
    int get_instance(vector<int>& a,vector<int>& b)
    {
        return  abs(a[0] - b[0]) + abs(a[1] - b[1]);
    }
};