算法	时间复杂度	有向图/无向图	边权（正/负）	单源/多源
Dijkstra	朴素：$O(N^{2})$ 队列优化：$O(NlogN)$	有向图、无向图	正	单源
Floyd-Warshall	$O(N^{3})$	有向图、无向图	正、负	多源
Bellman-Ford	$O(	V	\	E	)$	有向图	正、负	单源
SPFA	最坏：$O(	V	\	E	)$	有向图	正、负	单源

题目：
743. 网络延迟时间
1368. 使网格图至少有一条有效路径的最小代价
1928. 规定时间内到达终点的最小花费

1.Dijkstra

不能处理负权值图，主要用于处理单源最短路径。

1.1 朴素Dijkstra（邻接矩阵）

时间复杂度：$O(n^{2})$

算法流程：

1.首先，Dijkstra算法需要从当前所有未确定最短路的点中（与源点相邻），找到距离源点最短的点$x$。

2.其次，通过点$x$更新其他所有点距离源点的最短距离（都加上源点到点$x$的距离）。

3.当全部其他点都遍历完成后，一次循环结束，将$x$​标记为已经确定了最短路。进入下一轮循环，直到全部点都被标记为确定了最短路。

实现要求：

1.Dijkstra算法需要存储各个边权，可选择用「邻接矩阵」或「邻接表」来存储。「邻接矩阵」中，g[i][j]存储从点i到j的距离，若两点没有给出有向边，则g[i][j]置为INF。

2.需要记录所有点到源点的最短距离，使用一个数组来存储，dist[i]表示从源点到i点的最短距离，初始值置为INF，源点置为0。

3.使用标记数组used来表示某一点是否已经确定了最短路，防止重复计算。

4.INF设为Integer.MAX_VALUE / 2，防止更新最短距离时int溢出。

final int INF = Integer.MAX_VALUE / 2;

// 初始化邻接矩阵(n个点，编号从1到n)
int[][] g = new int[n + 1][n + 1];
for (int i = 1; i <= n; i++) {
	Arrays.fill(g[i], INF);
}

// 写入边的信息
for (int[] edge : edges) {
    // edge = (起点，终点，权值)
    int x = edge[0], y = edge[1], w = edge[2];
    g[x][y] = w;
}

// 初始化距离数组，表示到源点的距离
int[] dist = new int[n + 1];
Arrays.fill(dist, INF);
// 源点距离初始化为0
int start = k; // 源点编号
dist[start] = 0;

// 标记数组
boolean[] used = new boolean[n + 1];

// Dijkstra
for (int i = 1; i <= n; i++) {
    // 在还未确定最短路的点中，找到距离最小的点
    int x = -1;
    for (int y = 1; y <= n; y++) {
        if (!used[y] && (x == -1 || dist[y] < dist[x])) {
            x = y;
        }
    }
    // 用上面的最近点更新其他所有点
    used[x] = true;
    for (int y = 1; y <= n; y++) {
        dist[y] = Math.min(dist[y], dist[x] + g[x][y]);
    }
}
// 完成上面操作后就可以计算出所有点到源点的最短距离 dist[i].

1.2 使用优先队列优化的Dijkstra（邻接表）

时间复杂度：$O(mlogn)$​

1.2.1 使用哈希表实现（常数大）

// 构造邻接表
HashMap<Integer, HashMap<Integer, Integer>> adj = new HashMap<>();
for (int[] edge : edges) {
    int start = edge[0], end = edge[1], w = edge[2];
    adj.putIfAbsent(start, new HashMap<>());
    adj.get(start).put(end, w);
}
// 父节点数组，表示从源点到该点的最短路径中，该点的上一个节点
int[] parent = new int[n + 1];
// 初始距离数组
int[] dist = new int[n + 1];
Arrays.fill(dist, INF);

// 优先队列，存放终点和权重，到源点距离最小的排在前面
PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]); 
// 加入源点
q.offer(new int[] {k , 0, -1});

// Dijkstra, 每一次都会确定一个点到源点的最终最短距离
while (!q.isEmpty()) {
    int[] now = q.poll();
    int end = now[0], w = now[1], papa = now[2];
    if (dist[end] != INF) continue; // 已经有最小距离
    dist[end] = w; // 更新到累加过后的最短距离
    parent[end] = papa;
    //  更新以当前点为起点的点到源点的距离，即当前点到源点的距离加上当前点到下一个点的距离
    for (Map.Entry<Integer, Integer> en : adj.getOrDefault(end, new HashMap<>()).entrySet()) {
        int next = en.getKey(), next_w = en.getValue();
        q.offer(new int[] {next, w + next_w, end});
    }
}

1.2.2 使用列表实现

List<List<int[]>> adj = new ArrayList<>();
int[] dist = new int[n + 1];
for (int i = 0; i <= n; i++) {
    adj.add(new ArrayList<>());
    dist[i] = INF;
}
for (int[] edge : times) {
    adj.get(edge[0]).add(new int[] {edge[1], edge[2]});
}
PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
q.offer(new int[] {k, 0});
while (!q.isEmpty()) {
    int[] now = q.poll();
    if (dist[now[0]] != INF) continue;
    dist[now[0]] = now[1];
    for (int[] next : adj.get(now[0])) {
        q.offer(new int[]{next[0], next[1] + now[1]});
    }
}

2.Floyd-Warshall算法(邻接矩阵)

时间复杂度：$O(n^{3})$​​

空间复杂度：$O(n^{2})$

原理是「动态规划」，可以求出任意两点之间的最短距离，可以正确处理有向图或负权（但不可存在负权回路）的最短路径问题。

int INF = Integer.MAX_VALUE / 2;
int N = 110, M = 6010;
int[][] adj = new int[N][N];

// 构建邻接表
for (int i = 1; i <= n; ++i) {
    Arrays.fill(adj[i], INF);
    adj[i][i] = 0;
}
for (int[] edge : edges) {
    int x = edge[0], y = edge[1], w = edge[2];
    adj[x][y] = w;
}

// Floyd
for (int p = 1; p <= n; p++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            adj[i][j] = Math.min(adj[i][j], adj[i][p] + adj[p][j]);
        }
    }
}

3.Bellman-Ford

787. K 站中转内最便宜的航班

适用于有向图单源最短路径，可以处理边权重为负的情况。以边为单位，每次都找到从源点出发，进过[1~E]条边时的最短路径。因此也可以用于找带有限制条件的最短路问题，如最多经过多少个点（可以转换为最多经过多少条边）、最多经过多少条边等。

时间复杂度：$O(|V||E|)$

负权环判定与输出：因为负权环可以无限制的降低总花费，所以如果第n次操作仍可以降低花费，就一定存在负权环。

dist[V]
for i in V:
	if i == start:
		dist[i] = 0
    else:
    	dist[i] = INF
    	
for i in V:
	temp[V] = dist
	for e int E:
		if temp[e.end] > dist[e.start] + e.w:
			temp[e.end] = dist[e.start] + e.w
	dist = temp

SPFA（Shortest Path Faster Algorithm）：最短路径快速算法

使用队列优化的Bellman-ford算法。

SPFA:使用队列来进行优化剪枝，减少循环次数。

只能检测出负环。

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        List<List<int[]>> adj = new ArrayList<>();
        int[] cost = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
            cost[i] = Integer.MAX_VALUE;
        }
        for (int[] edge : times) {
            adj.get(edge[0]).add(new int[] {edge[1], edge[2]});
        }
        cost[k] = 0;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {k, cost[k]});
        while (!q.isEmpty()) {
            int[] now = q.poll();
            for (int[] next : adj.get(now[0])) {
                // 相当于剪枝操作
                if (cost[next[0]] > now[1] + next[1]) {
                    cost[next[0]] = now[1] + next[1];
                    q.offer(new int[] {next[0], cost[next[0]]});
                }
            }
        }
        int max = 0;
        for (int i = 1; i <= n; i++) {
            if (i == k) continue;
            max = Math.max(max, cost[i]);
        }
        return max == Integer.MAX_VALUE ? -1 : max;
    }
}