数据结构之图
系列文章目录
数据结构之ArrayList_arraylist o(1) o(n)-CSDN博客
数据结构之LinkedList-CSDN博客
数据结构之栈_栈有什么方法-CSDN博客
数据结构之队列-CSDN博客
数据结构之二叉树-CSDN博客
数据结构之优先级队列-CSDN博客
常见的排序方法-CSDN博客
数据结构之Map和Set-CSDN博客
数据结构之二叉平衡树-CSDN博客
数据结构之位图和布隆过滤器-CSDN博客
数据结构之并查集和LRUCache-CSDN博客
数据结构之B-树-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("=================");}}