2642. 设计可以求最短路径的图类

题目链接：2642. 设计可以求最短路径的图类

方法一：Dijkstra

解题思路

每次调用 \(shortestPath(st, ed)\) 时，就通过 \(Dijkstra\) 算法计算 \(st\) -> \(ed\) 的最短路。

代码

朴素写法

class Graph {
private:
    vector<vector<int>> adj;
    int e[110][110], n;
public:
    Graph(int n, vector<vector<int>>& edges){
        this->adj.resize(110);
        this->n = n;
        for (int i = 0; i < edges.size(); i ++ ) {
            int u = edges[i][0], v = edges[i][1], w = edges[i][2];
            adj[u].push_back(v);
            e[u][v] = w;
        }
    }
    
    void addEdge(vector<int> edge) {
        int u = edge[0], v = edge[1], w = edge[2];
        adj[u].push_back(v);
        e[u][v] = w;
    }
    
    int shortestPath(int st, int ed) {
        vector<int> isvisit(n), dist(n, INT_MAX);
        dist[st] = 0;
        while (1) {
            int tmp = INT_MAX, u = -1;
            for (int i = 0; i < n; i ++ ) { // 找剩余节点中dist最小的节点，加入集合，即st到当前节点的最短路已找到
                if (!isvisit[i] && dist[i] < tmp) {
                    tmp = dist[i];
                    u = i;
                }
            }
            if (u == -1) return -1; // 剩余节点无法到达
            if (u == ed) return tmp; // 已经找到st->ed的最短路
            isvisit[u] = 1;
            for (auto &v : adj[u]) { // 当前节点加入集合后，更新其邻接点的最短路大小
                if (!isvisit[v] && dist[u] + e[u][v] < dist[v]) {
                    dist[v] = dist[u] + e[u][v];
                }
            }
        }
    }
};

堆优化寻找剩余节点中 \(dist\) 最小节点的过程

class Graph {
private:
    vector<vector<int>> adj;
    int e[110][110], n;
public:
    Graph(int n, vector<vector<int>>& edges){
        this->adj.resize(110);
        this->n = n;
        for (int i = 0; i < edges.size(); i ++ ) {
            int u = edges[i][0], v = edges[i][1], w = edges[i][2];
            adj[u].push_back(v);
            e[u][v] = w;
        }
    }
    
    void addEdge(vector<int> edge) {
        int u = edge[0], v = edge[1], w = edge[2];
        adj[u].push_back(v);
        e[u][v] = w;
    }
    
    int shortestPath(int st, int ed) {
        vector<int> isvisit(n), dist(n, INT_MAX);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; // 堆优化
        dist[st] = 0;
        q.push({dist[st], st});
        while (1) {
            int tmp = INT_MAX, u = -1;
            if (!q.empty()) { // 找剩余节点中dist最小的节点，加入集合，即st到当前节点的最短路已找到
                auto front = q.top();
                q.pop();
                tmp = front.first;
                u = front.second;
            }
            if (u == -1) return -1;
            if (u == ed) return tmp;
            isvisit[u] = 1;
            for (auto &v : adj[u]) {
                if (!isvisit[v] && dist[u] + e[u][v] < dist[v]) {
                    dist[v] = dist[u] + e[u][v];
                    q.push({dist[v], v});
                }
            }
        }
    }
};

复杂度分析

时间复杂度：\(Graph()：O(m)，addEdge()：O(1)，shortestPath()：O(n^2)\)，堆优化：O(nlogn)；
空间复杂度：\(shortestPath()：O(n)\)。

方法二：Floyd

解题思路

每次调用 \(Graph()\) 时，就通过 \(Floyd\) 算法计算所有 \(x\) -> \(y\) 的最短路，然后在调用 \(addEdge()\) 时，判断是否需要更新相关的最短路。

class Graph {
private:
    vector<vector<int>> g;
    int n;
public:
    Graph(int n, vector<vector<int>>& edges) {
        // O(n^3)
        this->n = n;
        g = vector<vector<int>>(n, vector<int>(n, INT_MAX / 3));
        for (int i = 0; i < n; i ++ ) g[i][i] = 0;
        for (auto &e : edges)
            g[e[0]][e[1]] = e[2];
        for (int k = 0; k < n; k ++ ) 
            for (int i = 0; i < n; i ++ ) 
                for (int j = 0; j < n; j ++ ) 
                    g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
    }
    
    void addEdge(vector<int> e) {
        // O(n^2)
        int u = e[0], v = e[1], w = e[2];
        if (w >= g[u][v]) return ;
        g[u][v] = w;
        for (int i = 0; i < n; i ++ ) 
            for (int j = 0; j < n; j ++ ) 
                g[i][j] = min(g[i][j], g[i][u] + w + g[v][j]);
    }
    
    int shortestPath(int st, int ed) {
        // O(1)
        return g[st][ed] < INT_MAX / 3 ? g[st][ed] : -1;
    }
};