图论-最短路径算法

最短路 - OI Wiki

Floyd

n

for k in range(1, n + 1):
    for x in range(1, n + 1):
        for y in range(1, n + 1):
            f[x][y] = min(f[x][y], f[x][k] + f[k][y])

Dijkstra

基本代码

743. 网络延迟时间
BFS+优先队列 Dijkstra m*logm

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        int dis[] = new int[n+1];
        boolean vis[] = new boolean[n+1];
        Arrays.fill(dis, Integer.MAX_VALUE);
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1]-b[1]);
        ArrayList<int[]> edges[] = new ArrayList[n+1];
        for(int i = 0; i <= n; i++){
            edges[i] = new ArrayList<int[]>();
        }
        for(int time[] : times){
            edges[time[0]].add(new int[]{time[1], time[2]});
        }
        pq.offer(new int[]{k, 0});
        dis[k] = 0;
        while(!pq.isEmpty()){
            int tmp[] = pq.poll();
            int node = tmp[0], len = tmp[1];
            if(vis[node]) continue;
            vis[node] = true;
            for(int next[] : edges[node]){
                int nextnode = next[0];
                int edge = next[1];
                if(!vis[nextnode] && dis[nextnode] > dis[node]+edge){
                    dis[nextnode] = dis[node]+edge;
                    pq.offer(new int[]{nextnode, dis[nextnode]});
                }
            }
        }
        int v = 0;
        for(int i = 1; i <= n; i++){
            v = Math.max(v, dis[i]);
        }
        return v == Integer.MAX_VALUE? -1 : v;
    }
}

一/多源点 & 一/多汇点

方案：建立一个超级源点与一个超级汇点，超级源点与所有源点的距离为 0，超级汇点与所有汇点的距离为 0. 这样就只需要一次 Dijkstra 算法就完成了。如下图所示：

图论—（技巧）超级源点与超级汇点_偷得浮生半日闲,心情半佛半神仙！Peace And Coding！-CSDN博客_超级源点