[C++] Dijkstra's Minimax Path Algorithm
Minimum Spanning Trees and Minimax Paths\n\nThe path between any two nodes in a minimum spanning tree is a minimax path. That is, a path that minimizes the maxi
**Minimum Spanning Trees and Minimax Paths**\n\nThe path between any two nodes in a minimum spanning tree is a **minimax path**. That is, a path that minimizes the maximum weight of any of its edges (https://en.wikipedia.org/wiki/Widest_path_problem). \n\nHere is a proof:\nhttps://stackoverflow.com/questions/43012559/how-to-prove-there-always-exists-a-minimax-path-completely-on-the-mst\n\nIt follows from similar logic to that used in the proof that:\n* `e = (u, v, w)` is a *critical* edge if-and-only-if the cost of the minimax path from `u` to `v` that doesn\'t use `e` is *greater than* `w`.\n* `e = (u, v, w)` is a *pseudo-critical* edge if-and-only-if the cost of the minimax path from `u` to `v` that doesn\'t use `e` is *equal to* `w`.\n\n**Algorithm**\n\nFor every edge `e = (u, v, w)`, we remove `e` from the graph and find the cost of the minimax path from `u` to `v`.\n* If the cost if greater than `w`, then `e` is a critical edge.\n* If the cost is equal to `w` then `e` is a pseudo-critical edge.\n\nYou can find minimax paths with a trivial modification to Dijkstra\'s algorithm (and most other shortest-path algorithms).\n\n**C++**\n```c++\nclass Solution {\npublic:\n    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {\n        vector<vector<pair<int, int>>> g(n);\n        for (auto &e : edges) {\n            int u = e[0], v = e[1], w = e[2];\n            g[u].emplace_back(v, w);\n            g[v].emplace_back(u, w);\n        }\n        vector<vector<int>> ans(2);\n        for (int i = 0; i < edges.size(); i++) {\n            auto &e = edges[i];\n            int u = e[0], v = e[1], w = e[2];\n            int m = minimax(g, u, v);\n            if (w < m) {\n                ans[0].push_back(i);\n            } else if (w == m) {\n                ans[1].push_back(i);\n            }\n        }\n        return ans;\n    }\n\t\n    int minimax(vector<vector<pair<int, int>>> &g, int src, int dst) {\n        vector<int> dist(g.size(), 1e9);\n        priority_queue<pair<int, int>> pq;\n        pq.emplace(dist[src] = 0, src);\n        while (!pq.empty()) {\n            auto [pri, u] = pq.top(); pq.pop();\n            if (-pri > dist[u]) {\n                continue;\n            }\n            for (auto &[v, w] : g[u]) {\n                if (u == src && v == dst) {\n                    continue;\n                }\n                if (dist[v] > max(dist[u], w)) {\n                    dist[v] = max(dist[u], w);\n                    pq.emplace(-dist[v], v);\n                }\n            }\n        }\n        return dist[dst];\n    }\n};\n```
[]