多源最短路径

Floyd

统计 graph 图中任意两点之间的最短距离
动态规划思想：i，j 两点之间的最短距离，通过枚举中间点 k ，计算其最小值
动态方程：dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])
时间复杂度：O(n^3)
空间复杂度：O(n^2)
最终得到的结果是所有点之间的最短距离，可以输出路径，但是效率不高。
这种算法可以有负权路，但是不能有负权环

  1. import copy
  2. import time
  4. def floyd(graph):
  5.     dist = copy.deepcopy(graph)
  6.     for k in range(len(graph)): 
  7.         for i in range(len(graph)):
  8.             if dist[i][k] == INF: # 剪枝
  9.                 continue
  10.             for j in range(len(graph)):
  11.                 if dist[k][j] == INF: # 剪枝
  12.                     continue
  13.                 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 
  14.     return dist
  16. INF = float('inf')
  17. graph = [[0, 5, INF, 10],
  18.          [INF, 0, 3, INF],
  19.          [INF, INF, 0,   1],
  20.          [INF, INF, INF, 0]
  21.          ]
  22. floyd(graph)
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  5. #define M INT_MAX/2
  7. /*
  8. 该算法可以计算有负权的边，因为他对于每一组点的计算都是通过遍历所有点之后才确定的，因此有负权的边最终也会被正确的计算
  9. 但是，他不可以计算有负权环的图，因为每次都走负权环，则每次的路径都在减少，最终是无穷小
  10. */
  12. vector<vector<int>> floydFinder(vector<vector<int>>& dist)
  13. {
  14.     int n = dist.size();
  15.     vector<vector<int>> dp(dist);
  16.     vector<vector<int>> path(n, vector<int>(n, -1));
  17.     for (int k = 0; k < n; ++k)
  18.     {
  19.         for (int i = 0; i < n; ++i)
  20.         {
  21.             for (int j = 0; j < n; ++j)
  22.             {
  23.                 if (dp[i][j] > dp[i][k] + dp[k][j])
  24.                 {
  25.                     dp[i][j] = dp[i][k] + dp[k][j];
  26.                     path[i][j] = k;
  27.                 }
  28.             }   
  29.         }
  30.     }
  31.     return path;
  32. }
  34. void findPath(vector<vector<int>>& path, int start, int end, vector<int>& route)
  35. {
  36.     if (path[start][end] == -1)
  37.     {
  38.         if (route.empty())
  39.         {
  40.             route.push_back(start);
  41.             route.push_back(end);
  42.         }
  43.         else
  44.         {
  45.             route.push_back(end);
  46.         }
  47.         return;
  48.     }
  49.     else
  50.     {
  51.         int k = path[start][end];
  52.         findPath(path, start, k, route);
  53.         findPath(path, k, end, route);
  54.         return;
  55.     }
  56. }
  59. int main()
  60. {
  61.     vector<vector<int>> dist {
  62.         {0, 5, M, 10},
  63.         {M, 0, 3, M},
  64.         {M, M, 0, 1},
  65.         {M, M, M, 0}
  66.     };
  67.     vector<vector<int>> path = floydFinder(dist);
  68.     vector<int> route;
  69.     findPath(path, 0, 3, route);
  70.     for (auto& i: route)
  71.     {
  72.         cout << i << " ";
  73.     }
  74.     cout << endl;
  75. }

单源最短路径

Dijkstra

统计graph图中指定点的到其他点的最短距离
贪心算法思想,通过每次遍历贪心的选择距离 起点 最短距离的点作为指定点,然后确定其到其他点的最短距离.
时间复杂度:O(n^2 + E) E是每次确定最短距离点的时间复杂度(),可以使用小顶堆优化,这里使用的是直接遍历,即O(n),共遍历n次,因此E=O(n^2)
空间复杂度:O(n)
最终得到的结果是目标点到其余各点的最短距离，而不能输出路径
不能计算负权图，更不能计算负权环的图

INF = float('inf')
def dijkstra(point, graph):
    dist = list.copy(graph[point]) # point对应的点将会是0,dist中保存的是指定点到其他各点的直接距离
    check_dist = [False] * len(graph) # 统计已经确定的点
    check_dist[point] = True
    for i in range(len(graph)-1):
        min_index = findminindex(dist, check_dist) # 每次贪心的选择最短距离点
        if min_index == INF: # 此路不通...
            break
        check_dist[min_index] = True
        for v in range(len(graph)): # 以当前最短距离点为起始,更新dist中还未确定且原始指定点到该点的距离(dist[v])大于从原始指定点到当前最短距离点+当前最短距离点到该点的距离(dist[min_index]+graph[min_index][v])
            if check_dist[v] == False and graph[min_index][v] != INF and dist[v] > dist[min_index] + graph[min_index][v]:
                dist[v] = dist[min_index] + graph[min_index][v]
    return dist

def findminindex(dist, check_dist):
    temp_min = INF
    min_index = INF
    for index in range(len(dist)):
        if dist[index] < temp_min and check_dist[index] == False:
            temp_min = dist[index]
            min_index = index
    return min_index
graph = [[0, 5, INF, 10],
         [INF, 0, 3, INF],
         [INF, INF, 0,   1],
         [INF, INF, INF, 0]
         ]
dijkstra(0, graph)


# 使用优先队列优化:
def dijkstra(point, graph):
    dist = []
    for index in range(len(graph[point])):
        dist.append((graph[point][index], index)) # (val, index)
    heapq.heapify(dist) # heapq作为优先队列,将dist构建为小顶堆,dist[0]为最小距离点
    res_list = [INF] * len(graph)
    while dist:
        min_val, min_index = heapq.heappop(dist)
        res_list[min_index] = min_val
        if min_val == INF:  # 最小值已经为INF
            break
        for dist_index, (val, index) in enumerate(dist):
            if graph[min_index][index] != INF and val > min_val + graph[min_index][index]:
                dist[dist_index] = (min_val + graph[min_index][index], index)
        heapq.heapify(dist)
    return res_list

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

/*
如果使用Python实现将会更加容易，因为Python可以直接更新优先队列中的数，然后再调整堆即可
该算法是无法处理负权边的，因为我们每次选点都是基于：当前未找到的最短路的点中，距离源节点最近的点都是已经无法继续松弛的了
而如果存在负权边，比如[[0, 2, 3], [M, 0, M], [M, -2, 0]]，如果根据dijkstra的规则，首先计算的点将会是1，而其实0 -> 2 -> 1才是真正最短的距离
当前算法自然也就不可以处理负权环的问题了。

根据图的类型，分为两种方式：
1. 如果图是邻接矩阵(本题就是邻接矩阵)，一般是稠密图，也就是计算源节点到其他节点的距离都需要遍历，因此使用优先队列是没有什么意义的，都是O(n2)，如果是Python那种就有意义
2.如果图是邻接表，一般是稀疏图，因此使用优先队列就可以优化，因为我们可以根据点直接拿到他能到达的所有点，一般这么定义：vector<vector<pair<int, int>>> path; path里面包含的就是key能够到达的所有点的列表
见https://leetcode.cn/problems/network-delay-time/

*/

#define M INT_MAX/2


vector<int> dijkstraFinder(int point, vector<vector<int>>& dist)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Priority_Queue;
    vector<int> result(dist.size(), M);
    vector<bool> visited(dist.size(), false);
    Priority_Queue.emplace(0, point);
    while (!Priority_Queue.empty())
    {
        auto p = Priority_Queue.top();
        Priority_Queue.pop();
        if (p.first > result[p.second]) continue; // 因为这种做法可能会加入重复的点，因此需要忽略那些不合适的值
        result[p.second] = p.first;
        visited[p.second] = true;
        for (int i = 0; i < dist.size(); ++i)
        {
            if (visited[i]) continue;
            if (dist[p.second][i] + p.first <= dist[point][i])
            {
                Priority_Queue.emplace(dist[p.second][i] + p.first, i);
            }
        }
    }
    return result;
}

int main()
{
    vector<vector<int>> dist {
        {0, 5, M, 10},
        {M, 0, 3, M},
        {M, M, 0, 1},
        {M, M, M, 0}
    };
    vector<int> ret = dijkstraFinder(0, dist);
    for (auto& num: ret) cout << num << " ";
    cout << endl;
}

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        // 邻接表方式
        int M = INT_MAX / 2;
        vector<vector<pair<int, int>>> path(n);
        for (auto& v: times) path[v[0]-1].emplace_back(v[1]-1, v[2]);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> myQue;
        myQue.emplace(0, k-1);
        vector<int> dist(n, M);
        while (!myQue.empty())
        {
            auto p = myQue.top();
            myQue.pop();
            if (dist[p.second] < p.first) continue;
            dist[p.second] = p.first;
            for (auto& e: path[p.second])
            {
                int len = e.second + dist[p.second];
                if (len < dist[e.first])
                {
                    dist[e.first] = len;
                    myQue.emplace(len, e.first); 
                }
            }
        }
        int ret = 0;
        for (auto& num: dist) ret = max(ret, num);
        return ret == M ? -1 : ret;
    }
};

Bellman-Ford

算法的思想很简单就是直接遍历所有可能的点进行松弛操作，假设有N个点，E条边，则最终算法的时间复杂度为O(NE)，效率不高，但是可以处理负权边
要判断负权环，只需要在上面遍历完成之后更遍历一次，如果有任意一条边发生了更新，则说明有负权环。