用节点 A「更新」节点 B 的意思是，用起点到节点 A 的最短路长度加上从节点 A 到节点 B 的边的长度，去比较起点到节点 B 的最短路长度，如果前者小于后者，就用前者更新后者。这种操作也被叫做「松弛」。
1 2 3 4 5 6 7 8 9 10 11
function Dijkstra(G, w, s) // 实际上的操作是将每个除原点外的顶点置为无穷大 // d[v] = INF, d[0] = 0 INITIALIZE-SINGLE-SOURCE(G, s) S <- 空集 Q <- s // Q 是顶点V的优先队列，以顶点的最短路径估计排序 while(Q != 空集) do u <- EXTRACT - MIN(Q)// 取出最小点 S <- u for each vertex v 属于 Adj[u] doRELAX(u, v, w)// 松弛成功的结点会被加入到队列中
publicint networkDelayTime(int[][] times, int n, int k) { // 求出最长路径即可 // 距离为INF表示不可达，因为有相加的操作，故需要除2操作 int INF = Integer.MAX_VALUE / 2; // 邻接矩阵 int[][] g = newint[n][n]; for (int i = 0; i < n; i ++) { Arrays.fill(g[i], INF); } for (int[] time : times) { int x = time[0] - 1, y = time[1] - 1; g[x][y] = time[2]; } // 当前点到源点的距离 int[] dist = newint[n]; Arrays.fill(dist, INF); dist[k-1] = 0; // 已确定 boolean[] used = newboolean[n]; // 遍历n次，每次找到一个距离最短的点 for (int i = 0; i < n; i ++) { // 找到未确定点里的距离最短顶点 int x = -1; for (int y = 0; y < n; y ++) { if (!used[y] && (x == -1 || dist[y] < dist[x])) { x = y; } } // 标记最小距离点 used[x] = true; // 松弛操作：更新邻接点 for (int y = 0; y < n; y ++) { dist[y] = Math.min(dist[x] + g[x][y], dist[y]); } }
// 求出最大时间 int max = 0; for (intd : dist) { max = Math.max(d, max); } return max == INF ? -1 : max; }
publicint networkDelayTime(int[][] times, int n, int k) { // Dijkstra // 分为确定点和未确定点，每次去除最小未确定点，添加到确定点里并更新 int INF = Integer.MAX_VALUE / 2; // 邻接表 ArrayList<int[]>[] g = new ArrayList[n]; for (int i = 0; i < n; i ++) { g[i] = new ArrayList<>(); } for (int[] time : times) { int x = time[0] - 1; int y = time[1] - 1; g[x].add(newint[]{y, time[2]}); } // 与k的距离 int[] dist = newint[n]; Arrays.fill(dist, INF); dist[k-1] = 0;
// 未确定点 PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() { publicint compare(int[] a, int[] b) { // 路径相等时，索引小的放在前面 return a[1] == b[1] ? a[0] - b[0] : a[1] - b[1]; } }); pq.offer(newint[]{k-1, dist[k-1]}); while(!pq.isEmpty()) { int[] p = pq.poll(); int x = p[0], time = p[1]; // 已经确定过了 确定过的距离比当前距离小 if (dist[x] < time) { continue; } // 更新邻接点 for (int[] adj : g[x]) { int y = adj[0], dy = time + adj[1]; if (dy < dist[y]) { pq.offer(newint[]{y, dy}); dist[y] = dy; } } }
// 求出最大值 int max = 0; for (intd : dist) { max = Math.max(max, d); } return max == INF ? -1 : max; }
贝尔曼-福特算法（英语：Bellman–Ford algorithm），求解单源最短路径问题的一种算法，由理查德·贝尔曼（Richard Bellman） 和 莱斯特·福特 创立的。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为 Edward F. Moore 也为这个算法的发展做出了贡献。它的原理是对图进行 $|V|-1$次松弛操作，得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达$O(|V||E|)$。但算法可以进行若干种优化，提高了效率。
示例
网络延迟时间 有 n 个网络节点，标记为 1 到 n。 给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。 现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。
publicintnetworkDelayTime(int[][] times, int n, int k){ // Bellman-Ford 算法：以点拓展深度，以边拓展广度 int INF = Integer.MAX_VALUE / 2; int[] dist = newint[n]; Arrays.fill(dist, INF); dist[k-1] = 0;
// 拓展深度 for (int i = 0; i < n; i ++) { // 记录上次的距离 int[] pre = dist.clone(); // 拓展广度 for (int[] time : times) { int x = time[0]-1, y = time[1]-1, t = time[2]; dist[y] = Math.min(pre[x] + t, dist[y]); } }
// 求最大值 int max = 0; for (int d : dist) { max = Math.max(max, d); }
publicintnetworkDelayTime(int[][] times, int n, int k){ // Bellman-Ford 队列优化：只遍历松弛过的点 // 初始化 int INF = Integer.MAX_VALUE / 2; // 100个点，可以用邻接矩阵 int[][] g = newint[n][n]; for (int i = 0; i < n; i ++) { Arrays.fill(g[i], INF); } for (int[] time : times) { int x = time[0] - 1, y = time[1] - 1, w = time[2]; g[x][y] = w; } // 最短距离 int[] dist = newint[n]; Arrays.fill(dist, INF); dist[k-1] = 0; // 在队列中的点，无需再次入队 boolean[] inq = newboolean[n]; // 队列，松弛了且不在队列中的点，入队 Queue<Integer> q = new LinkedList<>(); q.offer(k-1); inq[k-1] = true; while (!q.isEmpty()) { int x = q.poll(); inq[x] = false; for (int y = 0; y < n; y ++) { if (y == x) continue; int dy = g[x][y] + dist[x]; if (dy < dist[y]) { dist[y] = dy; if (!inq[y]) { q.offer(y); inq[y] = true; } } } }
int max = -1; for (int d : dist) { max = Math.max(max, d); } return max == INF ? -1 : max; }
let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) for each vertex v dist[v][v] ← 0 for each edge(u,v) dist[u][v] ← w(u,v)// the weight of the edge (u,v) for k from 1 to |V| for i from 1 to |V| for j from 1 to |V| if dist[i][j] > dist[i][k] + dist[k][j] dist[i][j] ← dist[i][k] + dist[k][j] end if
在图论中，连通图基于连通的概念。在一个无向图 G 中，若从顶点 i 到顶点 j 有路径相连（当然从j到i也一定有路径），则称 i 和 j 是连通的。如果 G 是有向图，那么连接i和j的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。如果此图是有向图，则称为强连通图（注意：需要双向都有路径）。图的连通性是图的基本性质。
function MakeSet(x) x.parent := x x.rank := 0 end function function Union(x, y) xRoot := Find(x) yRoot := Find(y) if xRoot ≠ yRoot then if xRoot.rank < yRoot.rank then large := yRoot small := xRoot else large := xRoot small := yRoot end if small.parent := large if large.rank = small.rank then large.rank := large.rank + 1 end if end if end function
classSolution{ publicintfindCircleNum(int[][] isConnected){ int n = isConnected.length; // 初始化 UnionFind uf = new UnionFind(n); // 遍历两个点之间的关系，做处理 for (int i = 0; i < n; i ++) { for (int j = i + 1; j < n; j ++) { if (isConnected[i][j] == 1) { uf.union(i, j); } } }
classSolution{ publicintmakeConnected(int n, int[][] connections){ // 并查集 // 连接数小于n-1的必定不能链接，返回-1 // 连接数大约等于n-1的必定能链接，链接操作数等于不交集个数-1 // 遍历连接数，合并 int m = connections.length; if (m < n - 1) { return -1; } UnionFind nf = new UnionFind(n); for (int i = 0; i < m; i ++) { nf.union(connections[i][0], connections[i][1]); }
