leetcode algorithm-05

本文对图算法进行分析整理，包括：

单源最短路径：深度优先
单源最短路径：广度优先
单源最短路径：Dijkstra
单源最短路径：Bellman-Ford算法
单源最短路径：SPFA算法
多源最短路径：Floyd算法

图-总结

这个网络延迟时间算是最短路径题的典型，这里对图的各种算法进行记录和python\java实现，c++实现见github（补链接）。包括：

深度优先遍历BFS+广度优先遍历DFS
Dijkstra算法
Bellman-Ford算法
Floyd-Warshall算法
SPFA算法

首先是对算法的理解，在图算法上，一般都是建立邻接表和邻接矩阵，这一步骤在算法说明中省略。

单源最短路径：深度优先

一般都是采用递归函数遍历节点，给一个curTime，如果curTime<distance[i]，那么就会更新邻接表的所有元素，并且一直递归，直到不能更新即可。

带有权值的图，对其进行深度遍历，不用加vis来判定是否访问，只要对权值进行relaxation就行，可能会一直更新，因此时间复杂度为O(n^n)。
单源最短路径：广度优先

不同于递归的方式，采用BFS来修改所有可能会relaxation的元素，如果修改就加queue，不修改就不加。时间复杂度为O(n^n)。
单源最短路径：Dijkstra
单源最短路径：Bellman-Ford算法
单源最短路径：SPFA算法
多源最短路径：Floyd算法

深度优先遍历

class Solution:
    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
        adj = [[] for i in range(N+1)]
        distance = [float('inf') for i in range(N+1)]
        distance[0] = 0
        for time in times:
            adj[time[0]].append([time[1],time[2]])
        
        # 以start节点连接的边进行松弛操作
        # 如果最小时间更新了，那么后面的节点也要更新。
        # 这也是dfs的问题所在，一点更新后续都要更新。
        def dfs(start, curtime):
            if curtime >= distance[start]:
                return 
            distance[start] = curtime
            
            for item in adj[start]:
                dfs(item[0],curtime+item[1])
               
        dfs(K,0)
        if max(distance) != float('inf'):
            return max(distance)
        else:
            return -1

广度优先遍历

class Solution:
    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
        adj = [[] for i in range(N+1)]
        distance = [float('inf') for i in range(N+1)]
        distance[0] = 0
        for time in times:
            adj[time[0]].append([time[1],time[2]])
        
        # 以queue pop的节点对应的边进行松弛操作
        def bfs(start):
            distance[start] = 0
            queue = [start]
            while queue:
                temp = queue.pop(0)
                for node in adj[temp]:
                    if distance[temp] + node[1] < distance[node[0]]:
                        distance[node[0]] = distance[temp] + node[1]
                        queue.append(node[0])
                        # 如果没有更新，则无需再添加。
        
        bfs(K)
        if max(distance) != float('inf'):
            return max(distance)
        else:
            return -1

Dijkstra算法

思路：建立源点集S={start...}，选取距离最小的顶点k加入到S中，以k为新考虑的节点，对k相连的节点进行距离的比较，如更新的距离值小于原来的距离值，则修改路径。重复这个步骤直到所有节点加入到S中。

Dijkstra算法具有以下特性：

Dijkstra算法具有单向性，需要visited数组。因为贪心的思想，所以需要数学证明。如果存在负权值，Dijkstra无效。
Dijkstra算法可以采用堆优化，可见https://leetcode-cn.com/problems/network-delay-time/solution/gong-shui-san-xie-yi-ti-wu-jie-wu-chong-oghpz/
Dijkstra时间复杂度为O(n^2)，即每次对邻接节点进行修改。

class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        // 构建邻接矩阵，给边建立权重，这里采用数组直接声明
        int[][] graph = new int[N+1][N+1];
        for(int i=1; i<=N; i++){
            for(int j=1; j<=N; j++){
                graph[i][j] = -1;
            }
        }
        for(int[] time:times){
            graph[time[0]][time[1]]=time[2];
        }
        
        // distance表示当前节点到nodeset内节点的最短距离。
        // distance随着nodeset添加节点而更新。
        int[] distance = new int[N+1];
        Arrays.fill(distance,-1);
        for(int i=1; i<=N; i++){
            distance[i] = graph[K][i];
        }
        distance[K] = 0;
        boolean[] visited = new boolean[N+1];
        visited[K] = true;
        // 遍历除K节点的所有节点
        for(int i=1; i<=N; i++){
            int minDistance = Integer.MAX_VALUE;
            int minIndex = 1;
            // 寻找据当前节点最近的节点，没有访问过
            for(int j=1; j<=N; j++){
                if(!visited[j] && distance[j]!=-1 &&distance[j]<minDistance){
                    minDistance = distance[j];
                    minIndex = j;
                }
            }
            visited[minIndex] = true;
            // 对最小距离的节点相连的节点权重进行更新
            for(int j=1; j<=N; j++){
                if(graph[minIndex][j]!=-1){
                    if(distance[j] != -1){
                        distance[j] = Math.min(distance[j], distance[minIndex]+graph[minIndex][j]);
                    }else{
                        distance[j] = distance[minIndex] + graph[minIndex][j]; 
                    }
                }
            }
        }
        int Maxdistance = 0;
        for(int i=1; i<=N; i++){
            if(distance[i] == -1){
                return -1;
            }
            Maxdistance = Math.max(distance[i], Maxdistance);
        }
        return Maxdistance;
    }
}

Floyd算法

动态规划算法，对任意两点i,j间的路径有两种子状态，直接从i到j和从i-k-j两种状态，所以可以遍历中间节点，来松弛更新i到j的路径。

class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        // 构建邻接矩阵,初始化
        int[][] graph = new int[N+1][N+1];
        for(int i = 1; i < N + 1; i++){
            for(int j = 1; j < N + 1; j++){
                graph[i][j] = i==j? 0:-1;
            }
        }
        for(int[] time: times){
            graph[time[0]][time[1]] = time[2];
        }
        // 遍历所有节点，k代表中间节点,这里将采用k作为中间节点松弛
        for(int k = 1; k < N + 1; k++){
            for(int i = 1; i < N + 1; i++){
                for(int j= 1; j < N + 1; j++){
                    if(graph[i][k] != -1 && graph[k][j] != -1){
                        // 如果存在路径i-k-j路径，则进行松弛，否则建立路径。
                        if(graph[i][j] != -1){
                            graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
                        }else{
                            graph[i][j] = graph[i][k] + graph[k][j];
                        }
                    }
                }
            }
        }
        int maxDistance = 0;
        for(int i = 0; i < N + 1; i++){
            if(graph[K][i]==-1){
                return -1;
            }
            maxDistance = Math.max(maxDistance, graph[K][i]);
        }
        return maxDistance;
    }
}

Bellman-ford算法

思路：对所有的边（节点）进行松弛，每次松弛都会得到一条最短路径，每次松弛V-1次，若可以无限松弛，则说明包含负环。

步骤：初始化图，有起点s到各个顶点的距离dist(v)，对每个边进行松弛操作，即$dist(u)+w(u,b)<dist(v)$，遍历完成后，继续遍历，直到无法进行松弛为止。有点类似于循环BFS，是双向的，而Dijkstra算法效率相对来说就比较高，但是需要更好的数学证明。

class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        // 构建邻接矩阵，给边建立权重，这里采用数组直接声明
        // 邻接矩阵和邻接表不同，邻接矩阵一般采用直接遍历的方式
        int[] distance = new int[N+1];
        Arrays.fill(distance,-1);
        distance[K] = 0;
        
        // 进行松弛，每次进行N-1次松弛操作。
        for(int i = 1; i < N; i++){
            for(int[] time: times){
                int u = time[0];
                int v = time[1];
                int w = time[2];
                if(distance[u] != -1){
                    if(distance[v] != -1){
                        distance[v] = Math.min(distance[v], distance[u] + w);
                    } else {
                        distance[v] = distance[u] + w;
                    }
                }
            }
        }
        int maxDistance = 0;
        for(int i = 1; i < N + 1; i++){
            if(distance[i] == -1){
                return -1;
            }
            maxDistance = Math.max(distance[i],maxDistance);
        }
        return maxDistance;
    }
}

SPFA算法(Moore-Bellman-Ford算法)

思路：SPFA算法的基本思路与贝尔曼-福特算法相同，即每个节点都被用作用于松弛其相邻节点的备选节点。相较于贝尔曼-福特算法，SPFA算法的提升在于它并不盲目尝试所有节点，而是维护一个备选节点队列，并且仅有节点被松弛后才会放入队列中。整个流程不断重复直至没有节点可以被松弛。

针对Bellman-Ford简化了很多，这里只更新原来已经更新过的，类似于有限的BFS，最坏情况和Bellman-Ford算法相同的。

class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        int[][] graph = new int[N+1][N+1];
        for(int i = 1; i < N + 1; i++){
            for(int j = 1; j < N + 1; j++){
                graph[i][j] = i==j? 0:-1;
            }
        }
        for(int[] time: times){
            graph[time[0]][time[1]] = time[2];
        }
        // 按照 bellman-ford的思路，以k为原点。
        int[] distance = new int[N+1];
        Arrays.fill(distance, -1);
        distance[K] = 0;

        Queue<Integer> queue = new LinkedList<>();
        queue.add(K);
        while(!queue.isEmpty()){
            int curr = queue.poll();
            for(int i = 1; i < N + 1; i++){
                // 依照当前已经更新过的节点进行松弛，如果可以更改路径，则添加到队列中。
                if(graph[curr][i]!=-1 && (distance[i] == -1 || distance[i] > distance[curr]+graph[curr][i])){
                    distance[i] = distance[curr] + graph[curr][i];
                    if(!queue.contains(i)){
                        queue.add(i);
                    }
                }
            }
        }
        int maxDistance = 0;
        for (int i = 1; i <= N; i++) {
            if (distance[i] == -1) {
                return -1;  
            }
            maxDistance = Math.max(distance[i], maxDistance);
        }
        return maxDistance;
    }

图-总结