做网站的属于什么专业?,荥阳建设网站,seo入门课程,全屏企业网站图的概念
图是由顶点集合以及顶点之间的关系组成的一种数据结构#xff1a;G #xff08;V#xff0c;E#xff09; 其中 V 表示的是顶点集合 #xff1a; V { x | x 属于某个数据对象集} 是有穷非空集合 E 叫做边的集合 #xff1a; E {(x, y) | x, y 属于 V} 或者 …图的概念
图是由顶点集合以及顶点之间的关系组成的一种数据结构G VE 其中 V 表示的是顶点集合 V { x | x 属于某个数据对象集} 是有穷非空集合 E 叫做边的集合 E {(x, y) | x, y 属于 V} 或者 E {x, y | x, y 属于 V 并且 Path(x,y) 是顶点间关系的有穷集合也叫做边的集合}
(x,y) 表示 x 到 y 是一条双向通道即(x,y) 是无方向的Pathx,y 表示 x 到 y 的一条单向通道即Pathx,y 是有方向的
顶点和边图中结点称为顶点第i个顶点记作vi。两个顶点vi和vj相关联称作顶点vi和顶点vj之间有一条边 图中的第k条边记作ekek (vivj)或vivj。
有向图和无向图在有向图中顶点对x, y是有序的顶点对xy称为顶点x到顶点y的一条边(弧)x, y和y, x是两条不同的边比如下图G3和G4为有向图。在无向图中顶点对(x, y)是无序的顶点对(x,y) 称为顶点x和顶点y相关联的一条边这条边没有特定方向(x, y)和(yx)是同一条边比如下图G1和G2为 无向图。注意无向边(x, y)等于有向边x, y和y, x。 完全图在有n个顶点的无向图中若有n * (n-1)/2条边即任意两个顶点之间有且仅有一条边则称此图为 无向完全图 在n个顶点的有向图中若有n * (n-1)条边即任意两个顶点之间有且仅有方向相反的边则称此图为有向完全图。
邻接顶点在无向图中G中若(u, v)是E(G)中的一条边则称u和v互为邻接顶点并称边(u,v)依附于顶点u 和v在有向图G中若u, v是E(G)中的一条边则称顶点u邻接到v顶点v邻接自顶点u并称边u, v与 顶点u和顶点v相关联。
顶点的度顶点v的度是指与它相关联的边的条数记作deg(v)。在有向图中顶点的度等于该顶点的入度与 出度之和其中顶点v的入度是以v为终点的有向边的条数记作indev(v); 顶点v的出度是以v为起始点的有向 边的条数记作outdev(v)。因此dev(v) indev(v) outdev(v)。注意对于无向图顶点的度等于该顶点的入度和出度即dev(v) indev(v) outdev(v)。
路径在图G (V E)中若从顶点vi出发有一组边使其可到达顶点vj则称顶点vi到顶点vj的顶点序列为从 顶点vi到顶点vj的路径。
路径长度对于不带权的图一条路径的路径长度是指该路径上的边的条数对于带权的图一条路径的路 径长度是指该路径上各个边权值的总和。
简单路径与回路若路径上各顶点v1v2v3…vm均不重复则称这样的路径为简单路径。若路 径上 第一个顶点v1和最后一个顶点vm重合则称这样的路径为回路或环。
子图设图G {V, E}和图G1 {V1E1}若V1属于V且E1属于E则称G1是G的子图。 子图要求顶点齐全即可。 连通图在无向图中若从顶点v1到顶点v2有路径则称顶点v1与顶点v2是连通的。如果图中任意一 对顶点都是连通的则称此图为连通图。
强连通图在有向图中若在每一对顶点vi和vj之间都存在一条从vi到vj的路径也存在一条从vj到 vi的路 径则称此图是强连通图。
生成树一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条 边。
图的存储结构
存储图我们需要保存节点与关系节点与节点的关系是否连通是否带有权重图的存储结构有两种一种是邻接矩阵另一种是邻接表在后面图的算法中本文章会以邻接矩阵为例子提供演示。
邻接矩阵
无向图的邻接矩阵是对称的第i行(列)元素之和就是顶点i的度。有向图的邻接矩阵则不一定是对称 的第i行(列)元素之后就是顶点i 的出(入)度。0 表示不连通 1 表示连通 如果边带有权值并且两个节点之间是连通的上图中的边的关系就用权值代替如果两个顶点不通 则使用无穷大代替。 下面代码实现这里把自己和自己的距离也处理为无穷大方便后面算法的实现。 用邻接矩阵存储图的优点是能够快速知道两个顶点是否连通缺陷是如果顶点比较多边比较少时矩 阵中存储了大量的0成为系数矩阵比较浪费空间并且要求两个节点之间的路径不是很好求
分析实现
首先通过成员变量一个存储顶点的数组当然你也可以使用map 来进行映射因为后面要获取顶点下标当顶点个数一多效率就会低下 还有必不可少的邻接矩阵——二维数组用来保存边与边的关系 最后还要有一个布尔类型的变量因为图有两种要么是有向图要么是无向图所以这个变量来保存当前图的类型。
接着就是简单提供构造方法和初始化顶点数组
然后开始写添加边的代码添加边也很简单传入三个参数起始顶点目标顶点以及权重我们只要获取到顶点的下标将其对应到矩阵上就可以完成了但是要注意无向图的处理由于无向图是一个对称矩阵边与边的关系也是双向连通的所以要单独处理。
最后就是获取度注意的是有向图的度的获取有向图的度分为入度和出度。
最终代码
package graph;import java.util.Arrays;public class GraphByMatrix {public char[] arrayV;//顶点数组public int[][] matrix;//邻接矩阵public boolean isDirect;//是否为有向图//构造方法提供size : 顶点个数//arrayV 顶点数组public GraphByMatrix(int size,boolean isDirect) {this.arrayV new char[size];matrix new int[size][size];for (int i 0; i matrix.length; i) {Arrays.fill(matrix[i],Integer.MAX_VALUE);}this.isDirect isDirect;}//初始化顶点数组public void initArrayV(char[] arrayV) {for (int i 0; i arrayV.length; i) {this.arrayV[i] arrayV[i];}}//添加边public void addEdge(char srcV, char destV, int weight) {int indexSrc getIndexV(srcV);int indexDest getIndexV(destV);matrix[indexSrc][indexDest] weight;//无向图是对称矩阵单独处理if(!isDirect) {matrix[indexDest][indexSrc] weight;}}//获得下标private int getIndexV(char v) {for (int i 0; i arrayV.length; i) {if(arrayV[i] v) {return i;}}return -1;}//获得顶点的度public int getDegreeOfV(char v) {int count 0;int index getIndexV(v);for (int i 0; i matrix.length; i) {if(matrix[index][i] ! Integer.MAX_VALUE) {count;}}//有向图要单独处理入度if(isDirect) {for (int i 0; i matrix.length; i) {if(i ! index matrix[i][index] ! Integer.MAX_VALUE) {count;}}}return count;}public void printGraph() {for (int i 0; i arrayV.length; i) {System.out.print(arrayV[i] );}System.out.println();for (int i 0; i matrix.length; i) {for (int j 0; j matrix.length; j) {if(matrix[i][j] Integer.MAX_VALUE) {System.out.print(∞ );} else {System.out.print(matrix[i][j] );}}System.out.println();}}
}
邻接表
邻接表使用数组表示顶点的集合使用链表表示边的关系
注意无向图中同一条边在邻接表中出现了两次。如果想知道顶点vi的度只需要知道顶点vi边链表集 合中结点的数目即可。 有向图中每条边在邻接表中只出现一次与顶点vi对应的邻接表所含结点的个数就是该顶点的 出度也称出度表要得到vi顶点的入度必须检测其他所有顶点对应的边链表看有多少边顶点的dst 取值是i。
在代码的实现中我们不采用两张表而是使用一张表处理就是入边表。
分析实现
首先创建链表的结点起始位置目标位置权重next 域构造方法注意起始位置和目标位置采用 int 类型保存通过顶点数组来获取下标。
我们使用ArrayList 来实现邻接表保存链表。 使用char 类型的数组保存顶点 使用 Boolean 类型的变量保存图的类型。
注意ArrayList 的初始化要对每一个区域赋值为null如果不这样做ArrayList 内部的有效数据是为空的不是 null这会导致你后面的链表的插入发生越界访问
添加边 首先我们要先检查这个边是否已经保存进邻接表里了如果已经有了这条边就直接返回如果没有我们才继续进行添加添加边的时候我们采用头插法然后我们还需要进行考虑无向图因为无向图的边是双向关系的所以还要再添加一条边进去。
获得边的度 无向图直接遍历对应的链表即可。 但是如果是有向图我们还需要考虑入度的问题这时候上面求出了出度如果是有向图还需要遍历ArrayList 进行检查。
最终代码
package graph;import java.util.ArrayList;public class GraphByNode {static class Node{public int src;//起始位置public int dest;//目标位置public int weight;//权重public Node next;public Node(int src, int dest, int weight) {this.src src;this.dest dest;this.weight weight;}}public ArrayListNode edgeList;//邻接表public boolean isDirect;//是否为有向图public char[] arrayV;//顶点数组//构造方法//注意ArrayList 的处理如果不赋 null, ArrayList 的有效数据为 0 无法进行访问的public GraphByNode(int size, boolean isDirect) {this.edgeList new ArrayList(size);for (int i 0; i size; i) {edgeList.add(null);}this.isDirect isDirect;this.arrayV new char[size];}//初始化顶点数组public void initArrayV(char[] arrayV) {for (int i 0; i arrayV.length; i) {this.arrayV[i] arrayV[i];}}//添加边public void addEdge(char src, char dest, int weight) {int indexSrc getIndexOfV(src);int indexDest getIndexOfV(dest);addNode(indexSrc,indexDest,weight);//无向图再次添加if(!isDirect) {addNode(indexDest,indexSrc,weight);}}private void addNode(int indexSrc, int indexDest, int weight) {//首先判断这个节点是否存在Node cur edgeList.get(indexSrc);while(cur ! null) {if(cur.dest indexDest) {return;}cur cur.next;}//没有存储进行存储Node newNode new Node(indexSrc,indexDest,weight);newNode.next edgeList.get(indexSrc);edgeList.set(indexSrc,newNode);}//获取下标private int getIndexOfV(char v) {for (int i 0; i arrayV.length; i) {if(arrayV[i] v) {return i;}}return -1;}//获取度public int getDegreeOfV(char v) {int count 0;int index getIndexOfV(v);Node cur edgeList.get(index);while(cur ! null) {count;cur cur.next;}//有向图单独处理入度if(isDirect) {for (int i 0; i arrayV.length; i) {if (i ! index) {cur edgeList.get(i);while (cur ! null) {if (cur.dest index) {count;}cur cur.next;}}}}return count;}//打印邻接表public void printGraph() {for (int i 0; i arrayV.length; i) {Node cur edgeList.get(i);while(cur ! null) {System.out.print(cur.dest : cur.weight - );cur cur.next;}System.out.println();}}}
图的遍历 从这里开始我们以邻接矩阵为例子进行代码的讲解与分析。 图的遍历以无向图为例 广度优先遍历 广度优先遍历类似二叉树的层次遍历。
广度优先遍历的英文全称为 Breadth-First Search简写为 bfs
分析 类似二叉树的层次遍历在二叉树的层次遍历我们借助了一个队列这里我们也使用一个队列来保存顶点。
然后我们开始进行运行以下面的图为例
先从A开始遍历把A放入队列在出队列的同时遍历矩阵把B和C放入队列中然后进行B的出队列这时候又遍历矩阵B那行这时候A和C 进来了你会发现A重复进来了所以为例避免这种情况我们使用一个辅助数组来记录某个顶点是否被遍历了也就是在出队列和进队列的时候把这个顶点标记为 true,表示已经被遍历过了。 public void bfs(char src) {int n arrayV.length;boolean[] check new boolean[n];//辅助数组QueueCharacter queue new LinkedList();queue.offer(src);while(!queue.isEmpty()) {char ch queue.poll();System.out.print(ch );int index getIndexV(ch);check[index] true;for (int i 0; i n; i) {if(matrix[index][i] ! Integer.MAX_VALUE !check[i]) {queue.offer(arrayV[i]);check[i] true;}}}System.out.println();}深度优先遍历 深度优先遍历类似二叉树的前序遍历。
深度遍历英文全称为Depth First Search简写为 dfs
思路 使用一个辅助数据记录当前的顶点是否被访问过 然后我们使用递归每次遇到未被访问过的顶点进行递归处理。 public void dfs(char v) {boolean[] visited new boolean[arrayV.length];int index getIndexV(v);dfsChile(index,visited);}private void dfsChile(int index, boolean[] visited) {System.out.print(arrayV[index] -);visited[index] true;for (int i 0; i arrayV.length; i) {if(!visited[i] matrix[index][i] ! Integer.MAX_VALUE) {dfsChile(i,visited);}}}最小生成树
连通图中的每一棵生成树都是原图的一个极大无环子图即从其中删去任何一条边生成树 就不在连 通反之在其中引入任何一条新边都会形成一条回路。
若连通图由n个顶点组成则其生成树必含n个顶点和n-1条边。因此构造最小生成树的准则有三条
只能使用图中的边来构造最小生成树只能使用恰好n-1条边来连接图中的n个顶点选用的n-1条边不能构成回路
构造最小生成树的方法Kruskal算法和Prim算法。这两个算法都采用了逐步求解的贪心策略。
贪心算法是指在问题求解时总是做出当前看起来最好的选择。也就是说贪心算法做出的不是整体最优的 的选择而是某种意义上的局部最优解。贪心算法不是对所有的问题都能得到整体最优解。
Kruskal 算法
KrusKal 算法中文名称为克鲁斯卡尔算法
任给一个有n个顶点的连通网络N{V,E} 首先构造一个由这n个顶点组成、不含任何边的图G{V,NULL}其中每个顶点自成一个连通分量 其次不断从E中取出权值最小的一条边(若有多条任取其一)若该边的两个顶点来自不同的连通分量则将此边加入到G中。 如此重复直到所有顶点在同一个连通分量上为止。
核心每次迭代时选出一条具有最小权值且两端点不在同一连通分量上的边加入生成树。 Kruskal 算法采用的是全局贪心策略即每次都在全图中获取最小的边并且要求这条边不能构成一条回路。 我们来过一下Kruskal 算法的流程 纵观全图我们找到 h - g 这条边的全职最小将其纳入到最小生成树中 接着再次纵观全图发现 i - c 或者 g - f 这两条边都是最小将谁纳入到最小生成树都是可以的这里我们将 i - c 纳入。 纵观全图发现 g - f 最小纳入生成树中。 a - b 与 c - f 都是 4 将其一纳入即可这里纳入 a-b c-f 进入最小生成树中 然后你会发现这时候最小的边应该为 i - g 但是我们的最小生成树要求不能有环所以这条边不能纳入然后我们再继续找这时候 c - d 和 i - h 为最小边但是由于 i- h 纳入的话会构成环路所以只能将 c - d 纳入最小生成树中。 重复上面的动作最后得到下面的最小生成树 注意最小生成树的结果不是唯一的只要符合算法思想即可。 算法思路分析 首先我们需要从全图中找到一个最小的边我们可以使用优先级队列构建小根堆将全部的边纳入到图中通过出队列的方式获取最小的边。
然后我们需要判断最小的边会不会构成回路如果不会才能纳入到最小生成树中。 判断回路我们可以采用集合的方式如果这条边的两个顶点都在生成树的集合中就不能纳入这时候我们可以使用并查集来判断如果不了解并查集可以查阅这一篇博客 JavaDS —— 并查集 在每次纳入生成树的同时将这两个顶点纳入并查集中。
注意生成树要求 n 个顶点加 n- 1 条边这是有可能满足不了 n - 1 条边的就像下面的图一样D 点是隔离的无法实现最小生成树这时候你在构建最小生成树的结尾要判断是否构建好了最小生成树如果没有可以返回 -1 最终代码 //创建边类static class Edge {public int src;public int dest;public int weight;public Edge(int src, int dest, int weight) {this.src src;this.dest dest;this.weight weight;}}public int Kruskal(GraphByMatrix minTree) {//创建优先级队列PriorityQueueEdge queue new PriorityQueue(new ComparatorEdge() {Overridepublic int compare(Edge o1, Edge o2) {return o1.weight - o2.weight;}});//将所有的边纳入到优先级队列中int n arrayV.length;for (int i 0; i n; i) {for (int j 0; j n; j) {if(matrix[i][j] ! Integer.MAX_VALUE) {queue.offer(new Edge(i,j,matrix[i][j]));}}}UnionFindSet unionFindSet new UnionFindSet(n);//构建生成树int size 0;int totalWeight 0;while(!queue.isEmpty() size n - 1) {Edge tmp queue.poll();int src tmp.src;int dest tmp.dest;if(!unionFindSet.isSameSet(src,dest)) { minTree.addEdge(arrayV[src],arrayV[dest], tmp.weight);unionFindSet.union(src,dest);totalWeight tmp.weight;size;}}if(size n - 1) {return -1;}return totalWeight;}Prime 算法
Prime 算法 中文名称为 普里姆算法 Prime 算法采用局部贪心的策略。 我们来走一下这个算法的流程
首先给定一个初始的顶点这里给的是 a 然后从 d 开始寻找最小边得到 a - b将其纳入到最小生成树中。 然后我们得到最小生成树的集合为 {a,b}这时候 b 向外延伸 b - c 8, b - h 11, a - h 8经过比较b - c 和 a-h 都是最小边将其一纳入即可这里纳入的是 b-c
现在最小生成树的集合为 {a,b.c} c 开始延伸c - i 2 , c - f 4, c - d 7 并且和前面的 a-h 8 进行比较最后纳入 c - i 这条边。
i 延伸i - g 6, i - h 7 , 并且和前面的为被纳入的最小边集合进行比较最后将 c - f 纳入生成树中。 然后以此类推最后得到
算法分析 我们还是使用优先级队列保存边的关系但是prime 算法是每进一个顶点才会将新顶点所在的边关系全部入队。
首先先将初始顶点的边关系信息入队然后开始找最小边然后将最小边的信息纳入到生成树中并且与之对应的新顶点也要纳入到集合中新顶点的边关系也随之纳入进去。使用循环来进行操作。
最终代码 //创建边类static class Edge {public int src;public int dest;public int weight;public Edge(int src, int dest, int weight) {this.src src;this.dest dest;this.weight weight;}}public int prime(GraphByMatrix minTree, char src) {int totalWeight 0;int n arrayV.length;int size 0;//构建优先级队列PriorityQueueEdge queue new PriorityQueue(new ComparatorEdge() {Overridepublic int compare(Edge o1, Edge o2) {return o1.weight - o2.weight;}});UnionFindSet unionFindSet new UnionFindSet(n);int index getIndexV(src);for (int i 0; i n; i) {if(matrix[index][i] ! Integer.MAX_VALUE) {queue.offer(new Edge(index,i,matrix[index][i]));}}while(!queue.isEmpty()) {Edge tmp queue.poll();int indexSrc tmp.src;int indexDest tmp.dest;int weight tmp.weight;if(!unionFindSet.isSameSet(indexSrc,indexDest)) {unionFindSet.union(indexSrc,indexDest);minTree.addEdge(arrayV[indexSrc],arrayV[indexDest],weight);for (int i 0; i n; i) {if(matrix[indexDest][i] ! Integer.MAX_VALUE) {queue.offer(new Edge(index,i,matrix[index][i]));}}totalWeight weight;size;}}if(size n - 1) {return -1;}return totalWeight;}最短路径
最短路径问题从在带权图的某一顶点出发找出一条通往另一顶点的最短路径最短也就是沿路径各边的权值总和达到最小。
Dijkstra算法
迪杰斯特拉算法
单源最短路径问题给定一个图G ( V E ) G(VE)G(VE)求源结点s ∈ V s∈Vs∈V到图中每个结点v ∈ V v∈Vv∈V的最短路径。Dijkstra算法就适用于解决带权重的有向图上的单源最短路径问题同时算法要 求图中所有边的权重非负。一般在求解最短路径的时候都是已知一个起点和一个终点所以使用Dijkstra算法 求解过后也就得到了所需起点到终点的最短路径。
针对一个带权有向图G将所有结点分为两组S和QS是已经确定最短路径的结点集合在初始时为空初始 时就可以将源节点s放入毕竟源节点到自己的代价是0Q 为其余未确定最短路径的结点集合每次从Q 中找出一个起点到该结点代价最小的结点u 将u 从Q 中移出并放入S 中对u 的每一个相邻结点v 进行松 弛操作。松弛即对每一个相邻结点v 判断源节点s到结点u 的代价与u 到v 的代价之和是否比原来s 到v 的代 价更小若代价比原来小则要将s 到v 的代价更新为s 到u 与u 到v 的代价之和否则维持原样。如此一直循 环直至集合Q 为空即所有节点都已经查找过一遍并确定了最短路径至于一些起点到达不了的结点在算法 循环后其代价仍为初始设定的值不发生变化。Dijkstra算法每次都是选择V-S中最小的路径节点来进行更 新并加入S中所以该算法使用的是贪心策略。 Dijkstra算法存在的问题是不支持图中带负权路径如果带有负权路径则可能会找不到一些路径的最短路径。 public void dijkstra(char vSrc,int[] dist,int[] pPath) {int srcIndex getIndexV(vSrc);//距离数据初始化Arrays.fill(dist,Integer.MAX_VALUE);dist[srcIndex] 0;//路径数组初始化Arrays.fill(pPath,-1);pPath[srcIndex] 0;//当前顶点是否被访问过int n arrayV.length;boolean[] s new boolean[n];//n个顶点,要更新n次每次都要从0下标开始找到一个最小值for (int k 0; k n; k) {int min Integer.MAX_VALUE;int u srcIndex;for (int i 0; i n; i) {if(s[i] false dist[i] min) {min dist[i];u i;//更新u下标}}s[u] true;//u:s//松弛u连接出去的所有的顶点 vfor (int v 0; v n; v) {if(s[v] false matrix[u][v] ! Integer.MAX_VALUE dist[u] matrix[u][v] dist[v]) {dist[v] dist[u] matrix[u][v];pPath[v] u;//更新当前的路径}}}}Bellman-Ford算法
Dijkstra算法只能用来解决正权图的单源最短路径问题但有些题目会出现负权图。这时这个算法就不能帮助 我们解决问题了而bellman—ford算法可以解决负权图的单源最短路径问题。它的优点是可以解决有负权 边的单源最短路径问题而且可以用来判断是否有负权回路。它也有明显的缺点它的时间复杂度 O(N*E) (N是点数E是边数)普遍是要高于Dijkstra算法O(N²)的。像这里如果我们使用邻接矩阵实现那么遍历所有 边的数量的时间复杂度就是O(N^3)这里也可以看出来Bellman-Ford就是一种暴力求解更新。 public boolean bellmanFord(char vSrc,int[] dist,int[] pPath) {int srcIndex getIndexV(vSrc);//距离数据初始化Arrays.fill(dist,Integer.MAX_VALUE);dist[srcIndex] 0;//路径数组初始化Arrays.fill(pPath,-1);pPath[srcIndex] 0;int n arrayV.length;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];pPath[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;}Floyd-Warshall算法
Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。 Floyd算法考虑的是一条最短路径的中间节点即简单路径p{v1,v2,…,vn}上除v1和vn的任意节点。 设k是p 的一个中间节点那么从i到j的最短路径p就被分成i到k和k到j的两段最短路径p1p2。p1是从i到k且中间节 点属于{12…k-1}取得的一条最短路径。p2是从k到j且中间节点属于{12…k-1}取得的一条最短路 径。 Floyd算法本质是三维动态规划D[i][j][k]表示从点i到点j只经过0到k个点最短路径然后建立起转移方程然后通过空间优化优化掉最后一维度变成一个最短路径的迭代算法最后即得到所以点的最短路 public void floydWarShall(int[][] dist,int[][] pPath) {int n arrayV.length;for (int i 0; i n; i) {Arrays.fill(dist[i],Integer.MAX_VALUE);Arrays.fill(pPath[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];pPath[i][j] i;}else {pPath[i][j] -1;}if(i j) {dist[i][j] 0;pPath[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];//更新父节点下标//pPath[i][j] k;//不对//如果经过了 i-k k-j 此时是k//i-x-s-k k-..t-...x-jpPath[i][j] pPath[k][j];}}}}}
