計算機基礎速通--數據結構·圖的基礎應用二（基礎圖算法）

如有問題大概率是我的理解比較片面，歡迎評論區或者私信指正。

最近了解到了一個新的改變和提高自己的方法·時刻記錄不論多小的事情都記下，我目前用了4天，之前感覺一天天忙死但沒啥收獲，但是記錄了之后知道自己的時間花在了哪里，后期該如何調整，并且可以很好緩解焦慮情緒。

一、最小生成樹（最小代價樹）

1、基礎概念

最小生成樹基本概念：

MST的定義：權值和最小的生成樹（連通所有頂點、無環、邊數=頂點數-1、砍掉一條邊則不連通）。

性質：權值和唯一，但樹形可能不唯一（存在相同權值的邊時）。

適用場景：連通圖（非連通圖只有生成森林）。

Prim算法：

核心思想：貪心策略，從單個頂點逐步擴展，每次添加與當前樹連接的最小權值邊對應的頂點。

實現關鍵：

維護lowCost[]數組存儲頂點到生成樹的最小代價。
用isJoin[]標記頂點是否已加入樹（避免成環）。

時間復雜度：（適合稠密圖）。

Kruskal算法：

核心思想：貪心策略、按邊權升序選擇邊、避免成環。

實現關鍵：

邊排序。

用并查集（Union-Find）判斷邊的兩點是否連通。

時間復雜度：（適合稀疏圖）。

兩種算法對比：

適用場景：稠密圖用Prim，稀疏圖用Kruskal。

時間復雜度差異：Prim依賴頂點數，Kruskal依賴邊數。

2、Prim 算法（普?姆）

數據結構

lowCost[]：記錄各頂點加入生成樹的最小代價（初始：起點為0，直連頂點為邊權，非直連為∞）

isJoin[]：標記頂點是否已加入生成樹（初始：僅起點為true）

核心流程

for i in range(n-1):  # 共n-1輪# 1. 掃描lowCost找最小值頂點u（未加入的頂點）u = find_min(lowCost, isJoin)  isJoin[u] = True  # 加入生成樹# 2. 更新鄰接點v的lowCostfor v in graph[u]:if not isJoin[v] and graph[u][v] < lowCost[v]:lowCost[v] = graph[u][v]

時間復雜度

樸素實現：O(|V|^2)

堆優化：O(|E| log |V|)（用優先隊列存(lowCost, v)）

易錯點

初始化錯誤

未將起點lowCost設為0（誤設為∞）
未標記起點isJoin=True（導致重復加入）

更新邏輯錯誤

更新鄰接點時未檢查?isJoin[v]（已加入頂點不應更新）
錯誤更新非鄰接點（應只更新當前頂點的鄰接點）

非連通圖處理

未檢查是否加入所有頂點（若未完成但lowCost全為∞，說明圖不連通）

權值比較錯誤

更新時用邊權與舊lowCost比較（正確：graph[u][v] < lowCost[v]）
未處理重邊（應取最小權值邊）

基礎模板如下：

import java.util.*;public class PrimMST {// 樸素版Prim算法實現（O(V^2)）public static int prim(int[][] graph) {int n = graph.length;// 易錯點1：初始化 - 未正確設置起點會導致邏輯錯誤int[] lowCost = new int[n];      // 各頂點加入生成樹的最小代價boolean[] isJoin = new boolean[n]; // 標記頂點是否已加入生成樹Arrays.fill(lowCost, Integer.MAX_VALUE);lowCost[0] = 0; // 起點最小代價設為0（易錯點1.1：起點設為0）int totalCost = 0;int selectedCount = 0; // 已選頂點計數（用于檢測非連通圖）// 核心流程：共需選擇n個頂點（包括起點）for (int i = 0; i < n; i++) {// 1. 尋找當前lowCost中的最小值頂點uint u = -1;for (int v = 0; v < n; v++) {// 只考慮未加入的頂點（易錯點2：已加入頂點不能重復選擇）if (!isJoin[v] && (u == -1 || lowCost[v] < lowCost[u])) {u = v;}}isJoin[u] = true; // 將u加入生成樹totalCost += lowCost[u];selectedCount++;// 2. 更新u的鄰接點的lowCost值for (int v = 0; v < n; v++) {// 易錯點4：更新條件判斷（必須同時滿足三個條件）if (!isJoin[v] && graph[u][v] != 0 && graph[u][v] < lowCost[v]) {// 注意：graph[u][v]!=0 表示存在邊（0表示無直接邊）// 易錯點5：權值比較（需嚴格小于當前值才更新）lowCost[v] = graph[u][v];}}}// 易錯點3補充：檢查是否加入全部頂點if (selectedCount != n) {System.out.println("圖不連通！");return -1;}return totalCost;}public static void main(String[] args) {int[][] graph = {{0, 1, 5, 6},{1, 0, 5, 0},  // 易錯點7：無向圖需要對稱{5, 5, 0, 4},{6, 0, 4, 0}};int cost = prim(graph);if (cost != -1) {System.out.println("最小生成樹權值和: " + cost); // 正確結果：10}}
}

練習1：訓練Prim的二維坐標處理能力

1584. 連接所有點的最小費用 - 力扣（LeetCode）https://leetcode.cn/problems/min-cost-to-connect-all-points/description/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china

class Solution {public int minCostConnectPoints(int[][] points) {int n=points.length;//標記數組boolean[] isJion=new boolean[n];//最小代價數組int[] lowCost=new int[n];//初始化Arrays.fill(isJion,false);Arrays.fill(lowCost,Integer.MAX_VALUE);lowCost[0]=0;int selectedCount=0;//非連通圖檢測//記錄最終答案int ans=0;//prim算法for(int i=0;i<n;i++){//依次將lowCost中代價最小的節點加入生成樹int u=-1;//找出lowCost中代價最小的節點for(int v=0;v<n;v++){//節點未加入生成樹 && （第一次·生成樹的根節點 || 更小花費）if(!isJion[v] && (u==-1 || lowCost[v]<lowCost[u])){u=v;}}//加入生成樹并處理isJion[u]=true;ans+=lowCost[u];selectedCount++;//更新鄰接點的lowCostfor(int v=0;v<n;v++){if(!isJion[v] && cost(u,v,points)<lowCost[v]){lowCost[v]=cost(u,v,points);}}}return ans;}public int cost(int u,int v,int[][] points){return Math.abs(points[u][0]-points[v][0])+Math.abs(points[u][1]-points[v][1]);}
}

3、Kruskal 算法（克魯斯卡爾）

數據結構

邊集數組：按權值排序?edges = [(weight, u, v), ...]

并查集：判斷連通性（初始每個頂點獨立集合）

核心流程

edges.sort()  # 按權值升序排序
for weight, u, v in edges:if find(u) != find(v):  # 不連通union(u, v)         # 合并集合add_edge(u, v)      # 加入生成樹if edges_added == n-1: break  # 邊數達標終止

時間復雜度

排序：O(|E| log |E|)

并查集： $O(\alpha(|V|))$ 每輪（近似常數）

排序遺漏

未對邊排序直接遍歷（破壞貪心策略正確性）

并查集錯誤

未初始化并查集（每個頂點應為獨立集合）
合并后未更新父節點（需路徑壓縮優化）

環判斷錯誤

未檢查連通性直接加邊（應用并查集而非DFS/BFS判環）

終止條件缺失

未在邊數達n-1時提前終止（多余計算）

重邊處理

未去重直接排序（應保留最小權值重邊）

import java.util.*;public class KruskalMST {// 邊類static class Edge implements Comparable<Edge> {int src, dest, weight;public Edge(int src, int dest, int weight) {this.src = src;this.dest = dest;this.weight = weight;}@Overridepublic int compareTo(Edge other) {// 易錯點1：排序遺漏 - 必須按權值排序return this.weight - other.weight;}}// 并查集類static class UnionFind {int[] parent, rank;public UnionFind(int n) {parent = new int[n];rank = new int[n];// 易錯點2：并查集未初始化 - 每個頂點獨立集合for (int i = 0; i < n; i++) {parent[i] = i;  // 初始每個頂點獨立成集合}}public int find(int x) {// 路徑壓縮優化if (parent[x] != x) {parent[x] = find(parent[x]);}return parent[x];}public void union(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX == rootY) return;// 按秩合并if (rank[rootX] < rank[rootY]) {parent[rootX] = rootY;} else if (rank[rootX] > rank[rootY]) {parent[rootY] = rootX;} else {parent[rootY] = rootX;rank[rootX]++;}}}public static List<Edge> kruskal(List<Edge> edges, int n) {// 易錯點1：排序遺漏 - 必須先對邊排序Collections.sort(edges);UnionFind uf = new UnionFind(n);List<Edge> mst = new ArrayList<>();int edgesAdded = 0;for (Edge edge : edges) {// 易錯點3：環判斷錯誤 - 必須檢查連通性if (uf.find(edge.src) != uf.find(edge.dest)) {uf.union(edge.src, edge.dest);mst.add(edge);edgesAdded++;// 易錯點4：終止條件缺失 - 邊數達標提前終止if (edgesAdded == n - 1) break;}}// 檢查是否形成完整生成樹if (edgesAdded != n - 1) {System.out.println("圖不連通，無法形成最小生成樹");return null;}return mst;}public static void main(String[] args) {int n = 4;List<Edge> edges = new ArrayList<>();edges.add(new Edge(0, 1, 1));edges.add(new Edge(0, 2, 5));edges.add(new Edge(0, 3, 6));edges.add(new Edge(1, 2, 5));edges.add(new Edge(2, 3, 4));// 處理重邊（可選）// 易錯點5：重邊處理 - 保留最小權值邊// 本例無重邊，實際應用中需要預處理List<Edge> mst = kruskal(edges, n);if (mst != null) {System.out.println("最小生成樹邊集：");int totalWeight = 0;for (Edge edge : mst) {System.out.println(edge.src + " - " + edge.dest + " : " + edge.weight);totalWeight += edge.weight;}System.out.println("總權重: " + totalWeight); // 正確結果：4+2+4+4+4=18}}
}

練習2：掌握Kruskal并查集實現

1584. 連接所有點的最小費用 - 力扣（LeetCode）https://leetcode.cn/problems/min-cost-to-connect-all-points/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china

class Solution {public int minCostConnectPoints(int[][] points) {//極端if(points.length==0 || points==null)return 0;//邊List<Eadge> eadges=new ArrayList<>();//并查集UnionFind uf=new UnionFind(points.length);//終止條件int selectedCount=0;int ans=0;//初始化邊for(int v=0;v<points.length;v++){for(int u=v+1;u<points.length;u++){eadges.add(new Eadge(v,u,cost(v,u,points)));}}//排序Collections.sort(eadges);for(Eadge e:eadges){//判斷連通性if(uf.find(e.s)!=uf.find(e.e)){uf.union(e.s,e.e);selectedCount++;ans+=e.weight;}//終止if(selectedCount==points.length-1)break;}return ans;}public int cost(int u,int v,int[][] points){return Math.abs(points[u][0]-points[v][0])+Math.abs(points[u][1]-points[v][1]);}
}//邊類
class Eadge implements Comparable<Eadge>{int s;int e;int weight;public Eadge(int s,int e,int weight){this.s=s;this.e=e;this.weight=weight;}//重寫比較·升序@Overridepublic int compareTo(Eadge other) {return this.weight - other.weight;}
}//并查集類class UnionFind {//雙親數組·記錄當前下標節點的雙親節點下標int[] parent;//rank數組·union優化int[] rank;//初始化public UnionFind(int n){parent=new int[n];rank=new int[n];Arrays.fill(rank,0);//初始·每個節點都是獨立集合for(int i=0;i<n;i++){parent[i]=i;}}//查找·路徑優化public int find(int x){//終止條件·根節點的父節點是自己本身if(parent[x]!=x){parent[x]=find(parent[x]);}return parent[x];}//合并·高度壓縮（小樹并大樹上）public void union(int x,int y){//找根int v=find(x);int u=find(y);if(v==u)return ;//同一個集合不需要合并//檢查秩if(rank[v]<rank[u]){parent[v]=u;}else if(rank[v]>rank[u]){parent[u]=v;}else{parent[v]=u;rank[v]++;}}}

4、綜合練習·考察MST關鍵邊的理解

1489. 找到最小生成樹里的關鍵邊和偽關鍵邊 - 力扣（LeetCode）https://leetcode.cn/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree/description/

二、最短路徑

基礎

1.?算法適用場景

算法	無權圖	帶權圖	負權邊	負權回路	單源/多源
BFS	?	?	?	?	單源（無權圖）
Dijkstra	?	?	?	?	單源（帶權圖）
Floyd	?	?	?	?	多源（任意兩點）

2.?核心原理

BFS：層序遍歷，距離=層數（權值視為1）。
Dijkstra：貪心策略，每次選距離起點最近的未訪問點，更新鄰接點。
Floyd：動態規劃，A[k][i][j] = min(A[k-1][i][j], A[k-1][i][k] + A[k-1][k][j])。

3.?時間復雜度

算法	時間復雜度	空間復雜度
BFS	O(\|V\| + \|E\|)	O(\|V\|)
Dijkstra（基礎）	O(\|V\|2)	O(\|V\|)
Floyd	O(\|V\|3)	O(\|VBFS

BFS

問題1：“為什么DFS不適合？權值不等時為何BFS失效？”（為何BFS適合解決??無權圖單源最短路徑??（每條邊權值為1，路徑長度=邊數））

??答案??：DFS可能探索非最短路徑；權值不等時路徑長度≠邊數，需Dijkstra算法。

問題2：代碼中的??三個核心數組??

d[]：記錄源點到各頂點的最短距離（初始化為∞）。
visited[]：標記頂點是否被訪問（初始化為false）。
path[]：記錄路徑前驅（初始化為-1）。

if (!visited[w]) {d[w] = d[u] + 1;  // 更新距離path[w] = u;       // 記錄前驅visited[w] = TRUE;EnQueue(Q, w);
}

問題3：“BFS與Dijkstra在權值為1時的關系？”

??答案??：BFS是Dijkstra在無權圖中的特例（優先級隊列退化為普通隊列）。

問題4：若圖非連通，部分頂點d[]保持∞，如何處理？

??方法??：遍歷所有頂點，對未訪問頂點再次調用BFS。

問題5：

“如何輸出完整路徑？”→ 用path[]回溯。

“若需記錄多條最短路徑？”→ 將path[]改為存儲鏈表。

基礎代碼實現：

import java.util.*;public class BFSShortestPath {private List<List<Integer>> graph; // 鄰接表存儲圖結構private int[] dist;                // 存儲源點到各頂點的最短距離private int[] parent;              // 存儲最短路徑的前驅節點private boolean[] visited;         // 訪問標記數組public void bfsMinDistance(int start) {// 使用graph的大小（包含索引0）int n = graph.size();dist = new int[n];parent = new int[n];visited = new boolean[n];// 初始化Arrays.fill(dist, Integer.MAX_VALUE);Arrays.fill(parent, -1);Queue<Integer> queue = new LinkedList<>();dist[start] = 0;visited[start] = true;queue.offer(start);while (!queue.isEmpty()) {int u = queue.poll();// 安全遍歷（防止空指針）if (graph.get(u) != null) {for (int w : graph.get(u)) {if (!visited[w]) {dist[w] = dist[u] + 1;parent[w] = u;visited[w] = true;queue.offer(w);}}}}}// 重建最短路徑public List<Integer> getPath(int target) {LinkedList<Integer> path = new LinkedList<>();for (int v = target; v != -1; v = parent[v]) {path.addFirst(v);}return path;}// 圖初始化public static void main(String[] args) {BFSShortestPath bfs = new BFSShortestPath();int vertexCount = 8; // 頂點數量int arraySize = vertexCount + 1; // 數組大小=頂點數+1// 創建包含索引0~8的圖（共9個位置）bfs.graph = new ArrayList<>(arraySize);for (int i = 0; i < arraySize; i++) {bfs.graph.add(new ArrayList<>());}// 添加圖的邊（索引1~8對應頂點1~8）bfs.graph.get(1).add(2); bfs.graph.get(2).add(1);bfs.graph.get(1).add(5); bfs.graph.get(5).add(1);bfs.graph.get(2).add(6); bfs.graph.get(6).add(2);bfs.graph.get(6).add(3); bfs.graph.get(3).add(6);bfs.graph.get(6).add(7); bfs.graph.get(7).add(6);bfs.graph.get(3).add(4); bfs.graph.get(4).add(3);bfs.graph.get(7).add(8); bfs.graph.get(8).add(7);bfs.bfsMinDistance(2); // 從頂點2（索引2）開始System.out.println("從2到8的最短距離: " + bfs.dist[8]);System.out.println("路徑: " + bfs.getPath(8)); // [2, 6, 7, 8]}
}

練習：1091. 二進制矩陣中的最短路徑 - 力扣（LeetCode）https://leetcode.cn/problems/shortest-path-in-binary-matrix/

class Solution {//移動數組int[][] dir=new int[][]{{-1,1},{0,1},{1,1},{-1,0},{1,0},{-1,-1},{0,-1},{1,-1}};public int shortestPathBinaryMatrix(int[][] grid) {//起始判斷if(grid[0][0]==1)return -1;int n=grid.length;//路徑距離int[][] dist=new int[n][n];//路徑節點int[][][] path=new int[n][n][2];//標記數組boolean[][] visited=new boolean[n][n];//初始化for(int i=0;i<n;i++){Arrays.fill(dist[i],Integer.MAX_VALUE);}Deque<int[]> deque=new ArrayDeque<>();//起始節點入隊deque.add(new int[]{0,0});visited[0][0]=true;dist[0][0]=1;path[0][0]=new int[]{-1,-1};while(!deque.isEmpty()){//出隊int[] node=deque.poll();//處理int x=node[0],y=node[1];if(x==n-1 && y==n-1){PrintPath(grid,path);return dist[x][y];}//鄰居入隊for(int i=0;i<8;i++){int newx=x+dir[i][0];int newy=y+dir[i][1];//邊界if(newx<0 || newx>=n || newy<0 || newy>=n)continue;//符合條件的鄰居if(!visited[newx][newy] && grid[newx][newy]==0){deque.add(new int[]{newx,newy});dist[newx][newy]=dist[x][y]+1;visited[newx][newy]=true;path[newx][newy]=new int[]{x,y};}}}return -1;}//輸出路徑public void PrintPath(int[][] grid,int[][][] path){int n=grid.length;int x=path[n-1][n-1][0];int y=path[n-1][n-1][1];System.out.print("("+ (n-1) +", "+(n-1) +")"+"<-");while(x!=-1 && y!=-1){System.out.print("("+ x +", "+y +")"+"<-");int[] node=path[x][y];x=node[0];y=node[1];}}}

為了更加直觀，添加了路徑打印

Dijkstra

重點理解更新過程與負權圖的局限性

1. 初始化階段

易錯：漏掉不可達頂點的初始化

正確：dist[V] = ∞,?path[V] = -1

難點：源點到自身（dist[V0]=0）和直接鄰接點的處理

2. 頂點選擇（每輪循環）

易錯：選擇已確定頂點（final[i]=true的頂點不應再選）
難點：當存在多個相同dist值時，選擇任意一個均可（需說明）

3. 更新鄰接點

核心公式：
若 dist[i] + arcs[i][j] < dist[j]，則更新 dist[j] 和 path[j]
易錯：
- 未檢查final[j]==false
- 忽略不可達頂點（∞參與計算）
難點：理解"松弛操作"本質（通過新頂點縮短路徑）

4. 負權圖問題

負權值的破壞性??：

當存在負權邊（如 V?→V? 權值為 -5），已標記為?final=true的節點可能被??更短路徑推翻??

算法路徑：V?→V?（dist=7）

實際更優路徑：V?→V?→V?（10 + (-5) = 5）

但 V? 被提前標記為?final=true，導致無法更新：

import java.util.Arrays;public class DijkstraAlgorithm {// 使用鄰接矩陣存儲圖（易錯點1：需確保矩陣對稱性）private static final int INF = Integer.MAX_VALUE; // 表示無窮大public static void dijkstra(int[][] graph, int source) {int n = graph.length;int[] dist = new int[n];       // 最短路徑長度數組int[] path = new int[n];       // 前驅節點數組（易錯點2：需記錄路徑）boolean[] finalSet = new boolean[n]; // 已確定最短路徑的頂點集// 初始化三個核心數組（關鍵點1）Arrays.fill(dist, INF);Arrays.fill(path, -1);dist[source] = 0;  // 源點到自身距離為0// 主循環：執行n-1輪（關鍵點2）for (int count = 0; count < n - 1; count++) {// 步驟1：找當前dist最小的未確定節點int u = -1;int minDist = INF;for (int v = 0; v < n; v++) {if (!finalSet[v] && dist[v] <= minDist) { // 易錯點3：注意等號minDist = dist[v];u = v;}}if (u == -1) break; // 所有頂點已處理完finalSet[u] = true; // 標記為已確定// 步驟2：更新鄰接點（關鍵點3）for (int v = 0; v < n; v++) {// 易錯點4：需同時檢查4個條件if (!finalSet[v] &&graph[u][v] != INF &&dist[u] != INF &&dist[u] + graph[u][v] < dist[v]) {dist[v] = dist[u] + graph[u][v];path[v] = u; // 記錄前驅節點}}}// 打印結果（示例）printSolution(dist, path, source);}private static void printSolution(int[] dist, int[] path, int source) {System.out.println("源點: " + source);System.out.println("頂點\t距離\t路徑");for (int i = 0; i < dist.length; i++) {System.out.printf("%d\t%d\t", i, dist[i]);printPath(path, i);System.out.println();}}// 遞歸打印路徑（關鍵點4）private static void printPath(int[] path, int current) {if (current == -1) return;printPath(path, path[current]);System.out.print(current + " ");}public static void main(String[] args) {int[][] graph = {{0, 10, INF, INF, 5},{INF, 0, 1, INF, 2},{INF, INF, 0, 4, INF},{7, INF, 6, 0, INF},{INF, 3, 9, 2, 0}};dijkstra(graph, 0);}
}

練習：

743. 網絡延遲時間 - 力扣（LeetCode）https://leetcode.cn/problems/network-delay-time/description/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china

class Solution {public int networkDelayTime(int[][] times, int n, int k) {//異常判斷if(times.length==0 || times==null || k>n)return -1;//構建圖int[][] g=new int[n][n];final int INF =Integer.MAX_VALUE/2;for(int i=0;i<n;i++){Arrays.fill(g[i],INF);//g[x][y]==INF 無邊}for(int[] t:times){int x=t[0]-1,y=t[1]-1;g[x][y]=t[2];}//初始化boolean[] used=new boolean[n];//used[x]==true 存在x到源點最短距離int[] dist=new int[n];//dist[x] 源點到x最短距離Arrays.fill(dist,INF);dist[k-1]=0;int[] path=new int[n];Arrays.fill(path,-1);//計算其他n-1個節點的distfor(int i=0;i<n-1;i++){//找最短距離的鄰居（第一輪是初始節點）int u=-1;for(int v=0;v<n;v++){if(!used[v] && (u==-1 || dist[v]<dist[u]))u=v;}used[u]=true;//更新distfor(int j=0;j<n;j++){if(!used[j] && g[u][j]!=INF & dist[u]!=INF && dist[u]+g[u][j]<dist[j]){dist[j]=dist[u]+g[u][j];path[j]=u;}}}//直觀演示// Print(path,dist,k-1);int ans=Arrays.stream(dist).max().getAsInt();return ans==INF? -1:ans;}public void Print(int[] path,int[] dist,int source){System.out.println("源點: " + source);System.out.println("頂點\t距離\t路徑");for (int i = 0; i < dist.length; i++) {System.out.printf("%d\t%d\t", i, dist[i]);printPath(path, i);System.out.println();}}public void printPath(int[] path,int curr){if(curr==-1)return ;printPath(path,path[curr]);System.out.print(curr+"->");} 
}

Floyd

1、算法思想（建立直觀理解）

通過逐步增加中轉點，動態更新所有頂點之間的最短路徑。

初始化：假設一張地圖有多個城市（頂點），先記錄所有城市間直達的路徑長度（沒有直達記為無窮大）。

動態中轉：逐個考慮每個城市作為中轉站（比如先允許通過城市A中轉，再允許通過A和B中轉，以此類推）。

檢查優化：對于每一對城市（比如X到Y），檢查如果從X先到中轉站K，再從K到Y，總距離是否比當前已知的X到Y路徑更短。

如果更短：更新X到Y的最短路徑為?X->K->Y?的路徑，并記錄這個中轉站K；否則：保持原有路徑。

完成：當所有城市都作為中轉站被考慮過后，最終得到任意兩城市間的最短路徑。

想象你要為所有城市之間規劃最短快遞路線。Floyd的做法是：

第一輪：只允許快遞從起點直達終點。
第二輪：允許快遞在城市A中轉一次（比如?上海->A->廣州?可能比?上海->廣州?更快）。
第三輪：允許在城市A和B中轉，依此類推...
直到所有城市都可作為中轉站，最終得到全局最優路線。

關鍵：

能處理任意兩點間的最短路徑（單源/多源都適用）。
支持帶權圖（包括負權邊，但不能有負權環路）。
本質是動態規劃，通過三重循環實現（外層控制中轉點）。

可以去看看這個博主的講解，很直觀：

圖-最短路徑-Floyd(弗洛伊德)算法_嗶哩嗶哩_bilibilihttps://www.bilibili.com/video/BV19k4y1Q7Gj?spm_id_from=333.788.videopod.sections&vd_source=4b89f462036a892baf8931104a1f36b1

注意：視頻的path數組初始化和本文所采用的初始化方式不同（本文參考王道教材），但大體算法思路一致，可以參考。

算法演示：

Floyd-Warshall All-Pairs Shortest Pathhttps://www.cs.usfca.edu/~galles/visualization/Floyd.html

2、代碼實現·明確易錯點和難點

距離矩陣?`dist`

定義與初始化

int[][] dist = new int[n][n];

含義：dist[i][j]?表示從頂點?i?到頂點?j?的當前已知最短路徑長度
初始化：
- 如果?i == j，則?dist[i][j] = 0（頂點到自身距離為0）
- 如果存在邊?i→j，則?dist[i][j] = weight(i, j)（邊的權重）
- 如果不存在邊?i→j，則?dist[i][j] = Integer.MAX_VALUE（表示無窮大）

更新原理（動態規劃核心）

if (dist[i][k] + dist[k][j] < dist[i][j]) {dist[i][j] = dist[i][k] + dist[k][j];
}

物理意義：檢查通過中間點?k?的路徑是否比當前路徑更短
狀態轉移方程：

$dist^{(k)}[i][j] = \min \left( dist^{(k-1)}[i][j],\ dist^{(k-1)}[i][k] + dist^{(k-1)}[k][j] \right)$
動態規劃思想：當考慮允許通過頂點?k?中轉時，更新所有?i→j?的路徑

路徑矩陣?`path`

定義與初始化

int[][] path = new int[n][n];

含義：path[i][j]?記錄從?i?到?j?的最短路徑上的第一個中轉點
初始化：
- path[i][j] = -1?表示沒有中轉點（直接相連）
- path[i][j] = k?表示路徑?i→j?需要經過中轉點?k

更新原理

if (dist[i][k] + dist[k][j] < dist[i][j]) {path[i][j] = k;? // 記錄中轉點
}

關鍵點：當發現通過?k?中轉的路徑更短時，記錄這個關鍵中轉點
路徑重建原理：路徑信息是遞歸存儲的：
- 要獲取?i→j?的完整路徑，需要：
  1. 找到?path[i][j] = k
  2. 遞歸查找?i→k?的路徑
  3. 遞歸查找?k→j?的路徑

路徑重建算法

void printPath(int i, int j, int[][] path) {if (path[i][j] == -1) {System.out.print(j + " "); // 直接連接return;}int k = path[i][j];printPath(i, k, path); // 前半段路徑printPath(k, j, path); // 后半段路徑
}

import java.util.Arrays;public class FloydAlgorithm {public static void floyd(int[][] graph) {int n = graph.length;// 初始化距離矩陣（存儲最短路徑長度）int[][] dist = new int[n][n];// 初始化路徑矩陣（存儲中轉點）int[][] path = new int[n][n];// 易錯點1：正確初始化矩陣for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {dist[i][j] = graph[i][j];  // 復制原始圖// 難點1：路徑矩陣初始化// -1表示沒有中轉點（直接相連）path[i][j] = -1;}}// 核心三重循環// 易錯點2：循環順序必須是k->i->jfor (int k = 0; k < n; k++) {          // 考慮每個頂點作為中轉點for (int i = 0; i < n; i++) {      // 遍歷所有起點// 難點2：跳過無效路徑提升性能if (dist[i][k] == Integer.MAX_VALUE) continue;for (int j = 0; j < n; j++) {  // 遍歷所有終點// 跳過不可達路徑if (dist[k][j] == Integer.MAX_VALUE) continue;// 發現更短路徑// 易錯點3：避免整數溢出long newDist = (long) dist[i][k] + dist[k][j];if (newDist < dist[i][j]) {dist[i][j] = (int) newDist;path[i][j] = k;  // 記錄中轉點}}}}// 打印最終結果printSolution(dist, path);}// 遞歸打印路徑（難點3：路徑回溯）private static void printPath(int[][] path, int i, int j) {if (path[i][j] == -1) {System.out.print(" → " + j);return;}printPath(path, i, path[i][j]);  // 前半段路徑printPath(path, path[i][j], j);  // 后半段路徑}private static void printSolution(int[][] dist, int[][] path) {int n = dist.length;System.out.println("距離矩陣:");for (int[] row : dist) {System.out.println(Arrays.toString(row));}System.out.println("\n路徑矩陣:");for (int[] row : path) {System.out.println(Arrays.toString(row));}System.out.println("\n詳細路徑:");for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i != j && dist[i][j] != Integer.MAX_VALUE) {System.out.print(i + "→" + j + ": " + i);printPath(path, i, j);System.out.println(" (長度: " + dist[i][j] + ")");}}}}public static void main(String[] args) {// 示例圖（使用MAX_VALUE表示無窮大）int INF = Integer.MAX_VALUE;int[][] graph = {{0,   6,  13},{10,  0,   4},{5, INF,   0}};floyd(graph);}
}

3、練習1334. 閾值距離內鄰居最少的城市 - 力扣（LeetCode）https://leetcode.cn/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/?utm_source=LCUS&utm_medium=ip_redirect&utm_campaign=transfer2china

class Solution {public int findTheCity(int n, int[][] edges, int distanceThreshold) {//極端條件if(edges==null || edges.length==0)return 0;int INF=Integer.MAX_VALUE/2;//構建圖int[][] g=new int[n][n];for(int i=0;i<n;i++){Arrays.fill(g[i],INF);}for(int[] e:edges){int x=e[0],y=e[1];g[x][y]=e[2];g[y][x]=e[2];//無向圖}//距離數組int[][] dist=new int[n][n];//路徑數組·存中轉點int[][] path=new int[n][n];//初始化for(int i=0;i<n;i++){Arrays.fill(path[i],-1);}for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(i==j)dist[i][j]=0;else dist[i][j]=g[i][j];}}//floy流程for(int i=0;i<n;i++){//中轉點for(int s=0;s<n;s++){//源點if(dist[s][i]==INF)continue;//源點無法到達中轉點for(int e=0;e<n;e++){//終點if(dist[i][e]==INF)continue;//中轉點無法到達終點//更新dist與path·發現通過中轉點有更小的路徑就更新int curr=dist[s][i]+dist[i][e];if(curr<dist[s][e]){dist[s][e]=curr;path[s][e]=i;}}}}//結果int max_index=-1;int min_city=INF/2;for(int i=0;i<n;i++){int count=0;for(int j=0;j<n;j++){if(dist[i][j]<=distanceThreshold)count++;}if(count<=min_city){min_city=count;max_index=i;//i是遞增的}}// printSolution(dist,path);//可視化return max_index;}// 遞歸打印路徑private static void printPath(int[][] path, int i, int j) {if (path[i][j] == -1) {System.out.print(" → " + j);return;}printPath(path, i, path[i][j]);  // 前半段路徑printPath(path, path[i][j], j);  // 后半段路徑}private static void printSolution(int[][] dist, int[][] path) {int n = dist.length;System.out.println("距離矩陣:");for (int[] row : dist) {System.out.println(Arrays.toString(row));}System.out.println("\n路徑矩陣:");for (int[] row : path) {System.out.println(Arrays.toString(row));}System.out.println("\n詳細路徑:");for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i != j && dist[i][j] != Integer.MAX_VALUE) {System.out.print(i + "→" + j + ": " + i);printPath(path, i, j);System.out.println(" (長度: " + dist[i][j] + ")");}}}}
}