单源路径问题

全是正边

对于全是正边的题目，最短路问题上所有算法都行得通，主要看一个熟练度问题

最短

Floyd

基于动态规划的思想，从节点A到节点B的距离的最小值，等于所有途径AB之间起连通作用的点的路径的最小值，在小图里面非常好写，时间复杂度 $O(n^3)$

1
2
3
4
for k in range(1, N + 1):
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            f[i][j] = min(f[i][j], f[i][k] + f[k][j])

Bellman-Ford

每一轮都对边进行松弛操作 $dis(v) = min(dis(v), dis(u) + w(u, v))$ ，如果有负环则可以一直松弛下去，如果最后发现最后一轮还在松弛，说明进入了负环，时间复杂度是 $O(mn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
es = [[] for _ in range(N)]
dis = [inf] * N

bellman(n, s):
    dis[s] = 0
    f = False
    for i in range(1, n + 1):
        for st in range(1, n + 1):
            for to in es[st]:
                ed, w = to[0], to[1]
                if dis[ed] > dis[st] + w:
                    dis[ed] = dis[st] + w
                    f = True
        if not f:
            break
    return f

SPFA

对于Bellman算法，我们是不需要松弛所有边的，只有上一次松弛后的节点连接的边，才有可能被下一次松弛，因此可以使用队列进行优化，它只是上述算法的实现，时间复杂度不变

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
private boolean spfa(int n, int s) {
    boolean[] vi = new int[n + 1];
    int[] cnt = new int[n + 1];
    vi[s] = true;
    cnt[s] = 1;
    int[] dis = new int[n + 1];
    dis[s] = 0;
    Queue<Integer> q = new ArrayDeque<>();
    q.offer(s);
    while (!q.isEmpty()) {
        int i = q.poll();
        vi[i] = false;
        for (var to : es[i]) {
            int j = to[0], w = to[1];
            if (dis[j] > dis[i] + w) {
                dis[j] = dis[i] + w;
                cnt[j] = cnt[i] + 1;
                if (cnt[j] >= n) return true;
                if (!vi[j]) {
                    q.offer(j);
                    vi[j] = true;
                }
            }
        }
    }
    return false;
}

Dijkstra

最经典的最短路算法，使用优先队列优化，每次选择最小的状态进行松弛，时间复杂度 $O(mlogm)$

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
static int[] dis = new int[N];
static boolean[] vi = new boolean[N];
static int inf = Integer.MAX_VALUE;
static class Node {
    int i, w;
    public Node(int i, int w) {
        this.i = i;
        this.w = w;
    }
}
private void dijkstra(int s) {
    PriorityQueue<Node> q = new PriorityQueue<>((x, y) -> x.w - y.w);
    dis[s] = 0;
    Arrays.fill(dis, 1, n + 1, inf);
    q.offer(new Node(s, 0));
    while (!q.isEmpty()) {
        Node now = q.poll();
        int i = now.i;
        if (vi[i]]) continue;
        vi[i] = true;
        for (var to : es[i]) {
            int j = to[0], w = to[1];
            Node nxt = new Node(j, dis[i] + w);
            if (nxt.w < dis[j]) {
                dis[j] = nxt.w;
                q.offer(nxt);
            }
        }
    }
}

最长

由于我们讨论的图全是正边，对于所有的算法， 都可以通过把边全部取得相反数，然后跑最短路来获得绝对值最大的路，然后返回结果的相反数即可

存在负数边

最短

存在负数边的情况下，上述的算法Dijkstra无法进行最短路的求解了，那么同理它在有负数边的情况下也无法求解最长路

最长

上述算法除了Dijkstra都可以求解最长路

DAG

对于特殊的DAG而言，可以通过拓扑和动态规划更快地求得结果

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
es = [[] for _ in range(N)]
q = queue.Queue()
a = [] # 存放拓扑排序的结果
ind = [0] * n
for i in range(n):
    for e in es[i]:
        ind[e[0]] += 1
for i in range(n):
    if ind[i] == 0:
        q.put(i)
while not q.empty():
    i = q.get()
    a.append(i)
    for to in es[i]:
        ind[to[0]] -= 1
        if ind[to[0]] == 0:
            q.put(to[0])
mx = [-inf] * n
mn = [inf] * n

def f(s):
    mx[s] = 0
    mn[s] = 0
    for i in a:
        for to in es[i]:
            j, w = to[0], to[1]
            mx[j] = max(mx[j], mx[i] + w)
            mn[j] = min[mn[j], mx[i] + w]