＜原创＞ Leetcode:有向图中的最短路径解法（注释详细）_有向图走完所有节点路径最短

题目1,单源最短路径（Dijkstra ）：

1. 朴素的Dijksta算法（On^2）适合稠密图。

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        if(N==1) return 0;
        int inf = 10000;
        vector<vector<int>> g(N+1, vector<int>(N+1, inf));
        vector<int> dist(N+1, inf);  // 计算当前得到的各个点到第K个点的最短距离，之后不断刷新。
        vector<bool> st(N+1, false); // 确认各个点的当前得到的最短距离是否为最终确定的最短距离，是则true
        // st 也将 N个定点分成了两个集合A和B，A中的点已经确认了最短距离，B中点还未确定最短距离。
        for (auto &t : times)  g[t[0]][t[1]] = t[2]; // 构建邻接矩阵
        dist[K] = 0; // 起始点
        for (int i = 0; i < N-1; ++i) { // 还有N-1个点没有计算出最短距离，所以迭代N-1次
            int t = -1;
            for (int j = 1; j <= N; ++j) {
                //从集合B中挑出离K点最近的
                if (!st[j] && (t==-1 || dist[t] > dist[j])) t = j;
            }
            st[t] = true; // 第t个点确定为最短距离
            // 每次迭代 都从B集合中挑出离k最近的点t，然后其他点都以t点为中转站，更新到k点的最短距离dist
            for (int j = 1; j <= N; ++j) {
                dist[j] = std::min(dist[j], dist[t] + g[t][j]);
            }
        }
        int d_max = *std::max_element(dist.begin()+1, dist.end());
        return d_max == inf ? -1 : d_max;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

2.堆优化的Dijksta算法（Omlogn）适合稀疏图。

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        if(N==1) return 0;
        int inf = 10000;
        typedef pair<int, int> PII; // <距离，点号> ，距离放前面方便pair之间的大小比较 
        vector<int> dist(N+1, inf);  // 计算当前得到的各个点到第K个点的最短距离，之后不断刷新。
        vector<bool> st(N+1, false); // 确认各个点的当前得到的最短距离是否为最终确定的最短距离，是则true
        // st 也将 N个定点分成了两个集合A和B，A中的点已经确认了最短距离，B中点还未确定最短距离。
        unordered_map<int, vector<PII>> graph; // 邻接表
        priority_queue<PII, vector<PII>, greater<PII>> heap; // 保存每个点到k点的最小距离，小顶堆
        for (auto &t : times)  graph[t[0]].push_back({t[2], t[1]}); // 构建邻接表
        heap.push({0, K});
        dist[K] = 0; // 起始点
        while(!heap.empty()) {
            auto t = heap.top();
            heap.pop();
            int ver = t.second, distance = t.first;  // 当前 离 K点最近的点和距离
            if (st[ver]) continue; // 之前已经计算过，过
            st[ver] = true;
            for (auto &p : graph[ver]) { // 刷新 与ver点相连的点的最短距离
                if (dist[p.second] > distance + p.first) {
                    dist[p.second] = distance + p.first;
                    heap.push({dist[p.second], p.second});
                }
            }
        }
      
        int d_max = *std::max_element(dist.begin()+1, dist.end());
        return d_max == inf ? -1 : d_max;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

题目2,每个顶点对的最短路径（Floyd）：

class Solution {
    vector<vector<int>> graph;
    const int INF = 0x3f3f3f3f; 
    // 注意0x3f3f3f3f这个值比较特殊，可以视为无穷大。
public:
    vector<bool> checkIfPrerequisite(int n, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
        graph.resize(n, vector<int>(n, INF));
        for (auto &p : prerequisites) {
            graph[p[0]][p[1]] =  1;
        }
        for (int i = 0; i < n; ++i) graph[i][i] = 0;
        floyd(n);
        vector<bool> ans;
        for (auto &q : queries) {
            // 无论是否有负权值，这里都用 INF/2 ， 
            if (graph[q[0]][q[1]] > INF/2) ans.push_back(false);
            else ans.push_back(true);
        }
        return ans;
    }
    void floyd(int n) {
        // floyd 算法，n 次迭代，第 k 次使得 从 i 点到 j 点的距离在中转站只包括[0，k-1]的情况下最小
        // n 次迭代后，graph[i][j] 为 i点到j点最短距离，时间复杂度为O(n^3)
        // floyd 算法 求出了所有顶点对之间的最短距离，重复执行 Dijkstra 算法 n 次也可以求出，时间复杂度也是 O(n^3).
        for (int k = 0; k < n; ++k)
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

• 注意0x3f3f3f3f这个值比较特殊，可以视为无穷大。十进制是1061109567，也就是10^9 级别的（和0x7fffffff一个数量级），而一般场合下的数据都是小于10^9的，所以它可以作为无穷大使用而不致出现数据大于无穷大的情形。
• 事实上0x3f3f3f3f+0x3f3f3f3f=2122219134，这非常大但却没有超过32-bit int的表示范围，所以0x3f3f3f3f还满足了我们“无穷大加无穷大还是无穷大”的需求。
• 将无穷大设为0x3f3f3f3f，那么奇迹就发生了，0x3f3f3f3f的每个字节都是0x3f！所以要把一段内存全部置为无穷大，我们只需要memset(a,0x3f,sizeof(a))