算法笔记：最短路径、最小生成树与动态规划

最短路径

算法	时间复杂度	适用情况
Floyd 算法	O(v^3)，v 为顶点个数	单源，多源，负边权，负边权回路
Dijkstra 算法	O(v^2)	单源
Bellman-Ford 算法	O(ve)，e 为边的个数	单源，负边权
堆优化 Dijkstra 算法	O((v+e)*logv)	单源
SPFA 算法	时间复杂度不稳定	单源，负边权

Bellman–Ford 算法

不断尝试对图中的每一条边进行松弛。每进行一轮循环，就对图上所有的边都尝试进行一次松弛操作，当一次循环中没有成功的松弛操作时，算法停止：暴力遍历，无脑松弛。

每次循环是 O(|E|) 的，在最短路存在的情况下，由于一次松弛操作会使最短路的边数至少 +1，而最短路的边数最多为 |v|-1，因此整个算法最多执行 |v|-1 轮松弛操作。故总时间复杂度为 O(|v||e|)。

如果从起点 S 出发，抵达一个负环时，松弛操作会无休止地进行下去。注意到前面的论证中已经说明了，对于最短路存在的图，松弛操作最多只会执行 n-1 轮，因此如果第 n 轮循环时仍然存在能松弛的边，说明从 S 点出发，能够抵达一个负环，因此福特算法可以用来判断是否存在负权回路。

public class Main {
    static int n, m;
    static int[] dis;
    static Edge[] e;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        dis = new int[n + 5];
        e = new Edge[n * n + 5];
        for (int i = 0; i < m; i++) {
            e[i] =  ();
            e[i].x = scanner.nextInt();
            e[i].y = scanner.nextInt();
            e[i].w = scanner.nextInt();
        }
           scanner.nextInt(); 
        
        Arrays.fill(dis, Integer.MAX_VALUE / );
        dis[s] = ;
        ford();
         (   ; i <= n; i++) {
            System.out.print(dis[i] + );
        }
    }

        {
         x, y, w;
         flag;
        
         (   ; i <= n - ; i++) {
            flag = ;
             (   ; j < m; j++) {
                x = e[j].x;
                y = e[j].y;
                w = e[j].w;
                 (dis[x] + w < dis[y]) {
                    dis[y] = dis[x] + w;
                    flag = ;
                }
            }
            
             (!flag) {
                ;
            }
        }
    }
}

  {
     x, y; 
     w; 
}