系列文章目录
数据结构之ArrayList_arraylist o(1) o(n)-CSDN博客
前言
摘要：本文系统介绍了图的基本概念、存储结构和相关算法实现。主要内容包括：1) 图的邻接矩阵和邻接表两种存储方式及其Java实现；2) 图的广度优先和深度优先遍历算法；3) 最小生成树的Kruskal和Prime算法；4) 单源最短路径的Dijkstra、Bellman-Ford算法以及多源最短路径的Floyd-Warshall算法。文章详细阐述了各算法的设计思路和实现过程，并提供了完整的Java代码示例，涵盖了图论中的核心概念和典型应用场景。
一、图的基本概念
图是由顶点集合和顶点间关系组成的一种数据结构；
顶点：指图中的节点；
边：顶点和顶点之间的关联；
有向图：图中的边是有方向的；
无向图：图中的边是无方向的；
顶点的度：是和该顶点相连的边的条数；在有向图中是入度和出度的和；
路径：从顶点 A 出发到顶点 B 之间的顶点序列；
路径的长度：指边权值的总和；
简单路径：路径上的顶点不重复；
回路：路径上的第一个顶点和最后一个顶点重合；
连通图：无向图中任意两个顶点之间都是连通的；
强连通图：有向图中任意两个顶点都有出发的路径，也有回来的路径；
生成树：一个连通图的最小连通子图。有 n 个顶点的连通图的生成树，有 n 个顶点和 n - 1 条边；
二、图的存储
1. 邻接矩阵
邻接矩阵是一个二维数组，表示节点与节点之间的关系；
无向图的邻接矩阵是对称的，有向图的邻接矩阵不一定是对称的；
如果两个顶点之间带有权值，邻接矩阵就保存权值，如果不带有权值，邻接矩阵就保存无穷大；
邻接矩阵能够快速知道两个顶点是否连通；
2. 邻接矩阵的实现
arrayV 表示顶点数组；
matrix 表示邻接矩阵；
isDirect 表示是否为有向图，true 为有向图，false 为无向图；
GraphByMatrix(int size, boolean isDirect) 构造方法，给顶点数组分配空间，并将邻接矩阵初始化为整数的最大值，表示无穷大，设置是否为有向图；
initArrayV(char[] array): void 初始化顶点数组；
addEdge(char srcV, char destV, int weight): void 在邻接矩阵中添加边；
思路：
- 1. 获取 srcV 和 destV 在顶点数组中的下标，如果不存在，直接返回，不需要添加；
- 2. 设置对应坐标的权值；
- 3. 如果是无向图，在对称位置也设置权值；
getIndexOfV(char v): int 获取顶点 v 在顶点数组的下标；
getDevOfV(char v): int 获取顶点 v 的度；
思路：
- 1. 获取顶点 v 的下标；
- 2. 遍历顶点 v 下标对应的行，如果权值不为 0，度数加 1；
- 3. 如果是有向图，需要计算顶点的入度；
printGraph(): void 遍历邻接表并打印；
public class GraphByMatrix {
private char[] arrayV; // 顶点数组
private int[][] matrix; // 邻接矩阵
private boolean isDirect; // 表示是有向图/无向图
public GraphByMatrix(int size, boolean isDirect){
this.arrayV = new char[size];
this.matrix = new int[size][size];
for(int i = 0; i < size; i++){
Arrays.fill(matrix[i], Integer.MAX_VALUE);
}
this.isDirect = isDirect;
}
// 初始化顶点数组
public void initArrayV(char[] array){
int n = this.arrayV.length;
for(int i = 0; i < n; i++){
this.arrayV[i] = array[i];
}
}
public void addEdge(char srcV, char destV, int weight){
int src = getIndexOfV(srcV);
int dest = getIndexOfV(destV);
if(src == -1 || dest == -1){
return;
}
matrix[src][dest] = weight;
if(!isDirect){
matrix[dest][src] = weight;
}
}
private int getIndexOfV(int v){
int n = this.arrayV.length;
for(int i = 0; i < n; i++){
if(this.arrayV[i] == v){
return i;
}
}
return -1;
}
public int getDevOfV(char v){
int n = this.arrayV.length;
int count = 0;
int index = getIndexOfV(v);
for(int i = 0; i < n; i++){
if(matrix[index][i] != Integer.MAX_VALUE){
count++;
}
}
// 如果是有向图，需要计算入度
if(isDirect){
for(int i = 0; i < n; i++){
if(i == index){
continue;
}else{
if(matrix[i][index] != Integer.MAX_VALUE){
count++;
}
}
}
}
return count;
}
public void printGraph(){
int n = this.arrayV.length;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(matrix[i][j] == Integer.MAX_VALUE){
System.out.print("∞" + " ");
}else{
System.out.print(matrix[i][j] + " ");
}
}
System.out.println();
}
}
}3. 邻接表
使用数组表示顶点的集合，使用链表表示边的关系；
无向图中，同一条边，需要在邻接表中出现两次；顶点的链表中节点的数目就是顶点的度；
有向图中，顶点的链表中节点的数目是该顶点的出度；计算入度，必须遍历其它顶点的链表；
4. 邻接表的实现
邻接表是基于链表实现的，因此需要定义链表的节点；
src 起始顶点；
dest 目标顶点；
weight 顶点之间的权重；
next 下一个节点；
Node(char src, char dest, weight) 构造方法，初始化节点的起始顶点，目标顶点和权重；
arrayV 顶点数组；
edgeList 邻接表，使用一个 ArrayList<Node> 组织所有顶点的链表；
isDirect 表示是否为有向图；
GraphByNode(int size, boolean isDirect) 构造方法，给顶点数组分配空间，初始化邻接表，给每个顶点的起始位置放一个 null，设置是否为有向图；
initArrayV(char[] array): void 初始化顶点数组；
addEdge(char srcV, char destV, int weight): void 在邻接表中添加边；
思路：
- 1. 在邻接表中添加边；
- 2. 如果为无向图，需要在对称的位置也添加边；
addEdgeChild(char srcV, char destV, int weight): void 在邻接表中添加边；
思路：
- 1. 获取 srcV 和 destV 在顶点数组中的下标；
- 2. 遍历 srcV 对应的链表，如果找到了 destV，就表示这条边已经在链表中存在了，直接返回，如果没找到 destV，就头插到链表中；
getIndexOfV(char v): int 获取顶点 v 的下标；
getDevOfV(char v): int 获取顶点 v 的度；
思路：
- 遍历顶点 v 的链表，计算节点的个数，就是链表的度；
- 如果是有向图，上面只是计算了出度，还需遍历其余链表计算入度，如果找到了 v，度加 1；
printGraph(): void 遍历所有顶点的链表，打印节点；
public class GraphByNode {
static class Node{
public char src;
public char dest;
public int weight;
public Node next;
public Node(char src, char dest, int weight) {
this.src = src;
this.dest = dest;
this.weight = weight;
}
}
public char[] arrayV;
public List<Node> edgeList;
public boolean isDirect;
public GraphByNode(int size, boolean isDirect){
this.arrayV = new char[size];
this.edgeList = new ArrayList<>();
for(int i = 0; i < size; i++){
this.edgeList.add(null);
}
this.isDirect = isDirect;
}
// 初始化顶点数组
public void initArrayV(char[] array){
int n = this.arrayV.length;
for(int i = 0; i < n; i++){
this.arrayV[i] = array[i];
}
}
public void addEdge(char srcV, char destV, int weight){
addEdgeChild(srcV, destV, weight);
if(!isDirect){
addEdgeChild(destV, srcV, weight);
}
}
private void addEdgeChild(char srcV, char destV, int weight){
int src = getIndexOfV(srcV);
int dest = getIndexOfV(destV);
Node cur = edgeList.get(src);
while(cur != null){
if(cur.dest == destV){
return;
}
cur = cur.next;
}
Node node = new Node(srcV, destV, weight);
// 头插法
node.next = edgeList.get(src);
edgeList.set(src, node);
}
private int getIndexOfV(int v){
int n = this.arrayV.length;
for(int i = 0; i < n; i++){
if(this.arrayV[i] == v){
return i;
}
}
return -1;
}
// 获取顶点的度
public int getDevOfV(char v){
int index = getIndexOfV(v);
int count = 0;
Node cur = edgeList.get(index);
while(cur != null){
count++;
cur = cur.next;
}
// 如果是有向图，还需要统计入度
int n = this.arrayV.length;
if(isDirect){
for(int i = 0; i < n; i++){
if(i == index){
continue;
}else{
Node tmp = edgeList.get(i);
while(tmp != null){
if(tmp.dest == v){
count++;
}
tmp = tmp.next;
}
}
}
}
return count;
}
public void printGraph(){
int n = this.arrayV.length;
for(int i = 0; i < n; i++){
Node cur = edgeList.get(i);
System.out.print(cur.src + ": ");
while(cur != null){
System.out.print(cur.dest);
cur = cur.next;
}
System.out.println();
}
}
}三、图的遍历
基于邻接矩阵实现图的遍历；
1. 广度优先遍历
bfs(char v): void 从顶点 v 出发，针对图进行广度优点遍历；
思路：广度优先遍历通常需要借助队列实现，类似二叉树的层序遍历；
- 1. 建立一个队列，用于保存未打印的顶点；
- 2. 建立一个 boolean 数组，用于标记顶点是否遍历过；
- 3. 将顶点 v 入队，并将顶点 v 标记为 true；
- 4. 弹出队列中的顶点元素并打印，找到该顶点在顶点数组中的下标；
- 5. 遍历邻接矩阵中该顶点对应的行，找到通过边相连的（即邻接矩阵中不为无穷大），并且没有标记过的顶点（check[i] == false），加入队列，并标记为 true；
- 6. 重复4-5步骤，直至队列为空；
public void bfs(char v){
int n = this.arrayV.length;
Queue<Character> queue = new LinkedList<>();
boolean[] check = new boolean[n];
queue.offer(v);
int indexV = getIndexOfV(v);
check[indexV] = true;
while(!queue.isEmpty()){
char ch = queue.poll();
System.out.print(ch + " ");
int index = getIndexOfV(ch);
for(int i = 0; i < n; i++){
if(!check[i] && matrix[index][i] != Integer.MAX_VALUE){
queue.offer(this.arrayV[i]);
check[i] = true;
}
}
}
System.out.println();
}2. 深度优先遍历
dfs(char v): void 从顶点 v 出发，针对图进行深度优先遍历；
dfsChild(int index, boolean[] check): void 从 index 出发，针对图进行深度优先遍历；
思路：深度优先遍历，通常采用递归的形式，类似二叉树中的前中后序遍历；
- 1. 建立一个 boolean 数组，用于标记顶点是否遍历过；
- 2. 计算顶点 v 的下标；
- 3. 打印该顶点，并将 check 数组中该顶点对应下标的位置置为 true；
- 4. 遍历邻接矩阵中该顶点对应的行，找到通过边相连的，并且没有标记过的顶点，继续执行 3~4 步骤；
- 5. 整个过程不断找到符合要求的点进行深入搜索，直至找不到符合要求的点，返回到上一层；
- 6. 第一层遍历完成后，即完成了整幅图的深度优先遍历；
public void dfs(char v){
boolean[] check = new boolean[this.arrayV.length];
int index = getIndexOfV(v);
dfsChild(index, check);
}
public void dfsChild(int index, boolean[] check){
System.out.print(this.arrayV[index] + " ");
check[index] = true;
for(int i = 0; i < this.arrayV.length; i++){
if(!check[i] && matrix[index][i] != Integer.MAX_VALUE){
dfsChild(i, check);
}
}
}四、最小生成树
基于邻接矩阵实现；
1. 最小生成树
最小生成树是无向图中的概念；
连通图的每一棵生成树，都是原图的一个极大无环子图；
若连通图由 n 个顶点组成，生成树必包含 n 个顶点和 n - 1 条边；
n - 1 条边必须是图中的边，并且不能构成环；
构造最小生成树的方法：Kruskal 算法和 Prime 算法，两个算法都采用了贪心策略；
最小生成树是原图的一个极大无环子图，并不一定是唯一解；
2. Kruskal 算法
Kruskal 算法：每次找到图中的权值最小，并且两个顶点不在同一集合的边，加入生成树，直到找到 n - 1 条边；
贪心策略：每次找权值最小的边；
定义边的类：
srcIndex 边的起点；
destIndex 边的终点；
weight 边的权重；
Edge(int srcIndex, int destIndex, int weight) 构造方法，初始化起点，终点和权重；
static class Edge{
public int srcIndex;
public int destIndex;
public int weight;
public Edge(int srcIndex, int destIndex, int weight){
this.srcIndex = srcIndex;
this.destIndex = destIndex;
this.weight = weight;
}
}kruskal(GraphByMatrix minTree): int kruscal 算法求最小生成树；
思路：全局最优
- 1. 建立小根堆，遍历邻接矩阵，将所有的边存到小根堆，便于每次获取权重最小的边；
- 2. 建立一个并查集，用于检查边的两个顶点，是否处于同一个集合；
- 3. 如果两个边的顶点不在一个集合，在 minTree 中添加边，累加权重；
- 4. 将两个顶点加入同一集合；
- 5. 当边的条数不足 n - 1，并且小根堆不为空，重复 3~4 步骤；
- 6. 如果边的条数够 n - 1，返回权重，否则返回 -1，表示不存在最小生成树；
public int kruskal(GraphByMatrix minTree){
int n = this.arrayV.length;
// 1. 建小根堆 - 每次找到最小的边
PriorityQueue<Edge> minQ = new PriorityQueue<>((a, b) -> a.weight - b.weight);
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
if(matrix[i][j] != Integer.MAX_VALUE){
Edge edge = new Edge(i, j, matrix[i][j]);
minQ.offer(edge);
}
}
}
// 2. 每次拿到最小的边，判断是否在一个集合中
int count = 0;
UnionFindSet ufs = new UnionFindSet(n);
int totalWeight = 0;
while(count < n - 1 && !minQ.isEmpty()){
Edge edge = minQ.poll();
if(!ufs.isSameUnionFindSet(edge.srcIndex, edge.destIndex)){
minTree.addEdgeByIndex(edge.srcIndex, edge.destIndex, edge.weight);
ufs.union(edge.srcIndex, edge.destIndex);
totalWeight += edge.weight;
count++;
if(count == n - 1){
return totalWeight;
}
}
}
return -1;
}
private void addEdgeByIndex(int srcIndex, int destIndex, int weight){
matrix[srcIndex][destIndex] = weight;
if(!isDirect){
matrix[destIndex][srcIndex] = weight;
}
}3. Prime 算法
prime(GraphByMatrix minTree, char chV): int Prime 算法计算最小生成树；
思路：局部最优达到全局最优
- 1. 计算顶点 v 的下标，并加入到集合 setX，其余顶点的下标加入到集合 setY；
- 2. 建立小根堆，遍历邻接矩阵中顶点 v 对应的行，找到相连的顶点，加入小根堆；
- 3. 取出权重最小的边，如果 setX 不包含顶点 destIndex，就把这条边加入到最小生成树；
- 4. 把顶点 destIndex 加入到 setX 并从 setY 中删除；
- 5. 遍历邻接矩阵中 destIndex 顶点对应的行 ，找到和 dextIndex 连接的边，加入到小根堆；
- 6. 重复 3~5 步骤，直到找到 n - 1 条边，或者小根堆为空；
- 7. 如果找到 n - 1 条边，返回权重和，如果小根堆为空，返回 -1，表示不存在最小生成树；
public int prime(GraphByMatrix minTree, char chV){
int n = this.arrayV.length;
minTree.arrayV = this.arrayV;
// 1. 存放开始顶点
int index = getIndexOfV(chV);
Set<Integer> setX = new HashSet<>();
setX.add(index);
// 2. 存放未包含的顶点
Set<Integer> setY = new HashSet<>();
for(int i = 0; i < n; i++){
if(i == index){
continue;
}else{
setY.add(i);
}
}
// 3. 开始搜索起始顶点相连顶点
PriorityQueue<Edge> minQ = new PriorityQueue<>((a, b) -> a.weight - b.weight);
for(int j = 0; j < n; j++){
if(matrix[index][j] != Integer.MAX_VALUE){
Edge edge = new Edge(index, j, matrix[index][j]);
minQ.offer(edge);
}
}
// 4. 搜索相邻顶点
int count = 0;
int totalWeight = 0;
while(count < n - 1 && !minQ.isEmpty()){
Edge edge = minQ.poll();
if(!setX.contains(edge.destIndex)){
minTree.addEdge(this.arrayV[edge.srcIndex], this.arrayV[edge.destIndex], edge.weight);
setX.add(edge.destIndex);
setY.remove(edge.destIndex);
totalWeight += edge.weight;
count++;
System.out.println(this.arrayV[edge.srcIndex] + "->" + this.arrayV[edge.destIndex] + ", " + edge.weight);
if(count == n - 1){
return totalWeight;
}
for(int i = 0; i < n; i++){
if(matrix[edge.destIndex][i] != Integer.MAX_VALUE){
Edge tmp = new Edge(edge.destIndex, i, matrix[edge.destIndex][i]);
minQ.offer(tmp);
}
}
}
}
return -1;
}五、最短路径
从带权图的某一顶点出发，找到通往另一顶点的最短路径，最短路径指沿路径各边权值总和最小；
1. 单源最短路径 - Dijkstra 算法
vSrc 起始顶点；
dist 保存从 vSrc 出发到各个顶点的距离，默认为无穷大；
path 保存每个顶点的前一个顶点的下标，默认为 -1，起始顶点保存的值为 0；
dijkstra(char vSrc, int[] dist, int[] path): void 计算 vSrc 到其余顶点的最短距离和路径；
思路：
- 1. 计算顶点 vSrc 对应的下标 index；
- 2. 初始化 dist 数组，默认为无穷大，vSrc 对应的 dist 置为 0，表示 vSrc 到 vSrc 的距离为 0；
- 3. 初始化 path 数组，默认为 -1，vSrc 对应的 Path 置为 index，表示 vSrc 的前一个顶点是它自己；
- 4. 建立一个 boolean 数组，用来标记顶点是否已经确认找到最短路径；
- 5. 遍历 dist 数组，找到未标记顶点的距离的最小值和最小值的下标 u，将 check 对应位置置 true；
- 6. 松弛和 u 相连的边，如果起始顶点到 u 的距离，加上从 u 到 v 的距离，小于起始顶点到 v 的距离，就更新 dist[v]，并在 path 中，把 v 的上一个顶点更新为 u；
- 7. 重复 5~6 步骤 n 次，直到 boolean 数组全置为 true，表示找到从 vSrc 到所有顶点的最短距离和路径；
public void dijkstra(char vSrc, int[] dist, int[] path){
int n = this.arrayV.length;
boolean[] check = new boolean[n];
int index = getIndexOfV(vSrc);
// 初始化距离数组，和路径数组
Arrays.fill(dist, Integer.MAX_VALUE);
dist[index] = 0;
Arrays.fill(path, -1);
path[index] = index;
// n 个顶点，要找 n 次离得起点最近的点，每次找到之后都需要置 true，找到之后松弛连接的边
for(int i = 0; i < n; i++){
// 找到距离最近的顶点
int min = Integer.MAX_VALUE;
int u = index;
for(int j = 0; j < n; j++){
if(check[j] == false && min > dist[j]){
min = dist[j];
u = j;
}
}
check[u] = true;
// 松弛 u 顶点连接的边
for(int v = 0; v < n; v++){
if(check[v] == false && matrix[u][v] != Integer.MAX_VALUE
&& dist[u] + matrix[u][v] < dist[v]){
dist[v] = dist[u] + matrix[u][v];
path[v] = u;
}
}
}
}Dijkstra 算法不能解决图中存在负权值时的最短路径问题；因为负权值可能存在后效性，前面顶点确定的时候没有考虑这个问题；
printShortPath(char vSrc, int[] dist, int[] path): void 打印从 vSrc 到所有顶点的路径和权值；
思路：
- 1. 找到 vSrc 的下标；
- 2. 选取某个顶点，使用 ArrayList<Integer> 记录顶点的下标；
- 3. 根据 path 数组中存的值，记录顶点的前一个顶点；
- 4. 顶点的下标更新为前一个顶点的下标，重复 2~3 步骤，找到整条路径；
- 5. 逆置整条路径并打印；
- 6. 打印这条路径的权值和；
- 7. 重复 2~6 步骤，打印起始顶点到所有顶点的路径和权值和；
public void printShortPath(char vSrc, int[] dist, int[] path){
int n = this.arrayV.length;
int index = getIndexOfV(vSrc);
for(int i = 0; i < n; i++){
if(i == index) continue;
List<Integer> list = new ArrayList<>();
int pathI = i;
while(pathI != index){
list.add(pathI);
pathI = path[pathI];
}
list.add(index);
Collections.reverse(list);
for(int x : list){
System.out.print(this.arrayV[x] + "->");
}
System.out.println(dist[i]);
}
}2. 单源最短路径 - Bellman-Ford 算法
bellmanFord(char vSrc, int[] dist, int[] path): boolean 计算 vSrc 到其余顶点的最短距离和路径，找到返回 true，没找到返回 false；
思路：
- 1. 找到 vSrc 顶点的下标 idnex；
- 2. 初始化 dist 数组，默认为无穷大，vSrc 对应的 dist 置为 0，表示 vSrc 到 vSrc 的距离为 0；
- 3. 初始化 path 数组，默认为 -1，vSrc 对应的 Path 置为 index，表示 vSrc 的前一个顶点是它自己；
- 4. 遍历 dist 数组，计算从 顶点 i 到顶点 j 的距离，如果 i 到 j 存在边，起始点到 i 的距离，加上 i 到 j 的距离，小于起始点到 j 的距离，就更新 dist[j]，并更新 path[j] = i；
- 5. 后面的距离更新会影响前面的结果，因此重复 4 步骤 n 次，确保找到 vSrc 到所有顶点的最短距离和路径；
- 6. 完成 n 次更新时，要再找一次从 i 到 j 的最短距离，如果仍然存在更新距离的情况，表明当前图中存在负权回路，返回 false；不存在则返回 true；
public boolean bellmanFord(char vSrc, int[] dist, int[] path){
int index = getIndexOfV(vSrc);
Arrays.fill(dist, Integer.MAX_VALUE);
dist[index] = 0;
Arrays.fill(path, -1);
path[index] = index;
int n = this.arrayV.length;
// 更新 n 次，确保更新的结果
for(int k = 0; k < n; k++){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(matrix[i][j] != Integer.MAX_VALUE && dist[i] + matrix[i][j] < dist[j]){
dist[j] = dist[i] + matrix[i][j];
path[j] = i;
}
}
}
}
// 多搜一次，判断是否有负权回路
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(matrix[i][j] != Integer.MAX_VALUE && dist[i] + matrix[i][j] < dist[j]){
return false;
}
}
}
return true;
}Bellman-Ford 算法可以解决负权路径存在时的最短路径问题，但不能解决负权回路的问题，负权回路本身是不正常的情况；
3. 多源最短路径 - Floyd-Wallshall 算法
floydWallShall(int[][] dist, int[][] path): void 计算多源最短路径；
思路：采用动态规划的思想，选取某个顶点 k，讨论是否经过顶点 k，取两种情况的最小值；
- 1. 初始化 dist 数组为无穷大，path 数组为 -1；
- 2. 遍历邻接矩阵，如果 i 到 j 存在边，将边权填到 dist 数组中，并更新 path 数组；
- 3. 如果 i == j，将 dist[i][j] 更新为 0;
- 4. 如果从 i 顶点到 j 顶点经过 k 顶点，并且 i 到 k 的距离，加 k 到 j 的距离，小于 i 到 j 的距离，则更新 dist[i][j]，并更新 path 数组中顶点 j 的前一个顶点；
- 5. 重复 4 步骤 n 次，计算 从 i 顶点到 j 顶点经过 0~n-1 顶点的最短距离；
- 6. 打印经过某个顶点的距离和路径，分析是否正确；
public void floydWarShall(int[][] dist, int[][] path) {
int n = this.arrayV.length;
for (int i = 0; i < n; i++) {
Arrays.fill(dist[i], Integer.MAX_VALUE);
Arrays.fill(path[i], -1);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] != Integer.MAX_VALUE) {
dist[i][j] = matrix[i][j];
path[i][j] = i;
}else{
path[i][j] = -1;
}
if (j == i) {
dist[i][j] = 0;
path[i][j] = -1;
}
}
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] != Integer.MAX_VALUE
&& dist[k][j] != Integer.MAX_VALUE
&& dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
path[i][j] = path[k][j];
}
}
}
// 测试 打印权值和路径矩阵观察数据
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][j] == Integer.MAX_VALUE) {
System.out.print(" * ");
} else {
System.out.print(dist[i][j] + " ");
}
}
System.out.println();
}
System.out.println("=========打印路径==========");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(path[i][j] + " ");
}
System.out.println();
}
System.out.println("=================");
}
}