See More

- [1 并查集、图相关算法](#1) * [1.1 并查集](#11) + [1.1.1 并查集基本结构和操作](#111) + [1.1.2 例题](#112) * [1.2 图相关算法](#12) + [1.2.1 图的概念](#121) + [1.2.2 图的表示方法](#122) - [1.2.2.1 邻接表表示法](#1221) - [1.2.2.2 邻接矩阵表示法](#1222) + [1.2.3 图的遍历](#123) - [1.2.3.1 宽度优先遍历](#1231) - [1.2.3.2 深度优先遍历](#1232) + [1.2.4 图的拓扑排序](#124) + [1.2.5 图的最小生成树算法](#125) - [1.2.5.1 Kruskal（克鲁斯卡尔）算法](#1251) - [1.2.5.2 Prim算法](#1252) + [1.2.6 图的最短路径算法](#126) - [1.2.6.1 Dijkstra(迪杰特斯拉)算法](#1261) - [1.2.6.2 floyd算法](#1262)

1 并查集、图相关算法

1.1 并查集

1.1.1 并查集基本结构和操作

1、有若干个样本a、b、c、d...类型假设是V 2、在并查集中一开始认为每个样本都在单独的集合里 3、用户可以在任何时候调用如下两个方法： boolean isSameSet(V x, V y)：查询样本x和样本y是否属于一个集合 void union(V x, V y)：把x和y各自所在集合的所有样本合并成一个集合 4、isSameSet和union方法的代价越低越好，最好O(1) > 思路：isSameSet方法，我们设计为每个元素有一个指向自己的指针，成为代表点。判断两个元素是否在一个集合中，分别调用这两个元素的向上指针，两个元素最上方的指针如果内存地址相同，那么两个元素在一个集合中，反之不在 > 思路：union方法，例如将a所在的集合和e所在的集合合并成一个大的集合union(a,e)。a的代表点指针是a，e的代表点指针是e，我们拿较小的集合挂在大的集合下面，比如e小，那么e放在a的下面。链接的方式为小集合e头结点本来指向自己的代表节点，现在要指向a节点 > 并查集的优化点主要有两个，一个是合并的时候小的集合挂在大的集合下面，第二个优化是找某节点最上方的代表节点，把沿途节点全部拍平，下次再找该沿途节点，都变为O(1)。两种优化的目的都是为了更少的遍历节点。 > 由于我们加入了优化，如果N个节点，我们调用findFather越频繁，我们的时间复杂度越低，因为第一次调用我们加入了优化。如果findFather调用接近N次或者远远超过N次，我们并查集的时间复杂度就是O(1)。该复杂度只需要记住结论，证明无须掌握。该证明从1964年一直研究到1989年，整整25年才得出证明！算法导论23章，英文版接近50页的证明。 ```Java package class10; import java.util.HashMap; import java.util.List; import java.util.Stack; public class Code01_UnionFind { // 并查集结构中的节点类型 public static class Node { V value; public Node(V v) { value = v; } } public static class UnionSet { // 记录样本到样本代表点的关系 public HashMap> nodes; // 记录某节点到父亲节点的关系。 // 比如b指向a，c指向a，d指向a，a指向自身 // map中保存的a->a b->a c->a d->a public HashMap, Node> parents; // 只有当前点，他是代表点，会在sizeMap中记录该代表点的连通个数 public HashMap, Integer> sizeMap; // 初始化构造一批样本 public UnionSet(List values) { // 每个样本的V指向自身的代表节点 // 每个样本当前都是独立的，parent是自身 // 每个样本都是代表节点放入sizeMap for (V cur : values) { Node node = new Node<>(cur); nodes.put(cur, node); parents.put(node, node); sizeMap.put(node, 1); } } // 从点cur开始，一直往上找，找到不能再往上的代表点，返回 // 通过把路径上所有节点指向最上方的代表节点，目的是把findFather优化成O(1)的 public Node findFather(Node cur) { // 在找father的过程中，沿途所有节点加入当前容器，便于后面扁平化处理 Stack> path = new Stack<>(); // 当前节点的父亲不是指向自己，进行循环 while (cur != parents.get(cur)) { path.push(cur); cur = parents.get(cur); } // 循环结束，cur是最上的代表节点 // 把沿途所有节点拍平，都指向当前最上方的代表节点 while (!path.isEmpty()) { parents.put(path.pop(), cur); } return cur; } // isSameSet方法 public boolean isSameSet(V a, V b) { // 先检查a和b有没有登记 if (!nodes.containsKey(a) || !nodes.containsKey(b)) { return false; } // 比较a的最上的代表点和b最上的代表点 return findFather(nodes.get(a)) == findFather(nodes.get(b)); } // union方法 public void union(V a, V b) { // 先检查a和b有没有都登记过 if (!nodes.containsKey(a) || !nodes.containsKey(b)) { return; } // 找到a的最上面的代表点 Node aHead = findFather(nodes.get(a)); // 找到b的最上面的代表点 Node bHead = findFather(nodes.get(b)); // 只有两个最上代表点内存地址不相同，需要union if (aHead != bHead) { // 由于aHead和bHead都是代表点，那么在sizeMap里可以拿到大小 int aSetSize = sizeMap.get(aHead); int bSetSize = sizeMap.get(bHead); // 哪个小，哪个挂在下面 Node big = aSetSize >= bSetSize ? aHead : bHead; Node small = big == aHead ? bHead : aHead; // 把小集合直接挂到大集合的最上面的代表节点下面 parents.put(small, big); // 大集合的代表节点的size要吸收掉小集合的size sizeMap.put(big, aSetSize + bSetSize); // 把小的记录删除 sizeMap.remove(small); } } } } ``` ==并查集用来处理连通性的问题特别方便==

1.1.2 例题

学生实例有三个属性，身份证信息，B站ID,Github的Id。我们认为，任何两个学生实例，只要身份证一样，或者B站ID一样，或者Github的Id一样，我们都算一个人。给定一打拼学生实例，输出有实质有几个人？ > 思路：把实例的三个属性建立三张映射表，每个实例去对比，某个实例属性在表中能查的到，需要联通该实例到之前保存该实例属性的头结点下 ```Java package class10; import java.util.HashMap; import java.util.List; import java.util.Stack; public class Code07_MergeUsers { public static class Node { V value; public Node(V v) { value = v; } } public static class UnionSet { public HashMap> nodes; public HashMap, Node> parents; public HashMap, Integer> sizeMap; public UnionSet(List values) { for (V cur : values) { Node node = new Node<>(cur); nodes.put(cur, node); parents.put(node, node); sizeMap.put(node, 1); } } // 从点cur开始，一直往上找，找到不能再往上的代表点，返回 public Node findFather(Node cur) { Stack> path = new Stack<>(); while (cur != parents.get(cur)) { path.push(cur); cur = parents.get(cur); } // cur头节点 while (!path.isEmpty()) { parents.put(path.pop(), cur); } return cur; } public boolean isSameSet(V a, V b) { if (!nodes.containsKey(a) || !nodes.containsKey(b)) { return false; } return findFather(nodes.get(a)) == findFather(nodes.get(b)); } public void union(V a, V b) { if (!nodes.containsKey(a) || !nodes.containsKey(b)) { return; } Node aHead = findFather(nodes.get(a)); Node bHead = findFather(nodes.get(b)); if (aHead != bHead) { int aSetSize = sizeMap.get(aHead); int bSetSize = sizeMap.get(bHead); Node big = aSetSize >= bSetSize ? aHead : bHead; Node small = big == aHead ? bHead : aHead; parents.put(small, big); sizeMap.put(big, aSetSize + bSetSize); sizeMap.remove(small); } } public int getSetNum() { return sizeMap.size(); } } public static class User { public String a; public String b; public String c; public User(String a, String b, String c) { this.a = a; this.b = b; this.c = c; } } // (1,10,13) (2,10,37) (400,500,37) // 如果两个user，a字段一样、或者b字段一样、或者c字段一样，就认为是一个人 // 请合并users，返回合并之后的用户数量 public static int mergeUsers(List users) { UnionSet unionFind = new UnionSet<>(users); HashMap mapA = new HashMap<>(); HashMap mapB = new HashMap<>(); HashMap mapC = new HashMap<>(); for(User user : users) { if(mapA.containsKey(user.a)) { unionFind.union(user, mapA.get(user.a)); }else { mapA.put(user.a, user); } if(mapB.containsKey(user.b)) { unionFind.union(user, mapB.get(user.b)); }else { mapB.put(user.b, user); } if(mapC.containsKey(user.c)) { unionFind.union(user, mapC.get(user.c)); }else { mapC.put(user.c, user); } } // 向并查集询问，合并之后，还有多少个集合？ return unionFind.getSetNum(); } } ```

1.2 图相关算法

1.2.1 图的概念

1、由点的集合和边的集合构成 2、虽然存在有向图和无向图的概念，但实际上都可以用有向图来表达，无向图可以理解为两个联通点互相指向 3、边上可能带有权值

1.2.2 图的表示方法

对于下面一张无向图，可以改为有向图： ``` graph LR; A-->C C-->A C-->B B-->C B-->D D-->B D-->A A-->D ```

1.2.2.1 邻接表表示法

记录某个节点，直接到达的邻居节点： A: C,D B: C,D C: A,B D: B,A 如果是带有权重的边，可以封装我们的结构，例如A到C的权重是3,那么我们可以表示为A: C(3),D

1.2.2.2 邻接矩阵表示法

我们把不存在路径的用正无穷表示，这里用'-'表示，例如A到C的边权重是3，可把上图表示为： ``` A B C D A 0 0 3 - B - 0 0 0 C 3 0 0 - D 0 0 - 0 ``` > 图算法并不难，难点在于图有很多种表示方式，表达一张图的篇幅比较大，coding容易出错。我们的套路就是熟悉一种结构，遇到不同的表达方式，尝试转化成为我们熟悉的结构，进行操作 点结构的描述： ```Java package class10; import java.util.ArrayList; // 点结构的描述 A 0 public class Node { // 点的编号，标识 public int value; // 入度，表示有多少个点连向该点 public int in; // 出度，表示从该点出发连向别的节点多少 public int out; // 直接邻居：表示由自己出发，直接指向哪些节点。nexts.size==out public ArrayList nexts; // 直接下级边：表示由自己出发的边有多少 public ArrayList edges; public Node(int value) { this.value = value; in = 0; out = 0; nexts = new ArrayList<>(); edges = new ArrayList<>(); } } ``` 边结构的描述： ```Java package class10; // 由于任何图都可以理解为有向图，我们定义有向的边结构 public class Edge { // 边的权重信息 public int weight; // 出发的节点 public Node from; // 指向的节点 public Node to; public Edge(int weight, Node from, Node to) { this.weight = weight; this.from = from; this.to = to; } } ``` 图结构的描述： ```Java package class10; import java.util.HashMap; import java.util.HashSet; // 图结构 public class Graph { // 点的集合，编号为1的点是什么，用map public HashMap nodes; // 边的集合 public HashSet edges; public Graph() { nodes = new HashMap<>(); edges = new HashSet<>(); } } ``` 任意图结构的描述，向我们上述的图结构转化： 例如，我们有一种图的描述是，变的权重，从from节点指向to节点 ```Java package class10; public class GraphGenerator { // matrix 所有的边 // N*3 的矩阵 // [weight, from节点上面的值，to节点上面的值] public static Graph createGraph(Integer[][] matrix) { // 定义我们的图结构 Graph graph = new Graph(); // 遍历给定的图结构进行转换 for (int i = 0; i < matrix.length; i++) { // matrix[0][0], matrix[0][1] matrix[0][2] Integer weight = matrix[i][0]; Integer from = matrix[i][1]; Integer to = matrix[i][2]; // 我们的图结构不包含当前from节点，新建该节点 if (!graph.nodes.containsKey(from)) { graph.nodes.put(from, new Node(from)); } // 没有to节点，建立该节点 if (!graph.nodes.containsKey(to)) { graph.nodes.put(to, new Node(to)); } // 拿出我们图结构的from节点 Node fromNode = graph.nodes.get(from); // 拿出我们图结构的to节点 Node toNode = graph.nodes.get(to); // 建立我们的边结构。权重，from指向to Edge newEdge = new Edge(weight, fromNode, toNode); // 把to节点加入到from节点的直接邻居中 fromNode.nexts.add(toNode); // from的出度加1 fromNode.out++; // to的入度加1 toNode.in++; // 该边需要放到from的直接边的集合中 fromNode.edges.add(newEdge); // 把该边加入到我们图结构的边集中 graph.edges.add(newEdge); } return graph; } } ```

1.2.3 图的遍历

例如该图： ``` graph LR; A-->B A-->C A-->D B-->C B-->E C-->A C-->B C-->D C-->E ```

1.2.3.1 宽度优先遍历

1、利用队列实现 2、从源节点开始依次按照宽度进队列，然后弹出 3、每弹出一个点，把该节点所有没有进过队列的邻接点放入队列 4、直到队列变空 > 宽度优先的思路：实质先遍历自己，再遍历自己的下一跳节点(同一层节点的顺序无需关系)，再下下跳节点...... 我们从A点开始遍历： 1、A进队列--> Q[A]；A进入Set--> S[A] 2、A出队：Q[],**打印A**；A直接邻居为BCD,都不在Set中，进入队列Q[D,C,B], 进入S[A,B,C,D] 3、B出队：Q[D,C], B有CE三个邻居，C已经在Set中, 放入E, S[A,B,C,D,E]，队列放E, Q[E,D,C] 4、 C出队，周而复始 ```Java package class10; import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; public class Code02_BFS { // 从node出发，进行宽度优先遍历 public static void bfs(Node node) { if (node == null) { return; } Queue queue = new LinkedList<>(); // 图需要用set结构，因为图相比于二叉树有可能存在环 // 即有可能存在某个点多次进入队列的情况 HashSet set = new HashSet<>(); queue.add(node); set.add(node); while (!queue.isEmpty()) { Node cur = queue.poll(); System.out.println(cur.value); for (Node next : cur.nexts) { // 直接邻居，没有进入过Set的进入Set和队列 // 用set限制队列的元素，防止有环队列一直会加入元素 if (!set.contains(next)) { set.add(next); queue.add(next); } } } } } ```

1.2.3.2 深度优先遍历

1、利用栈实现 2、从源节点开始把节点按照深度放入栈，然后弹出 3、每弹出一个点，把该节点下一个没有进过栈的邻接点放入栈 4、直到栈变空 > 深度优先思路：表示从某个节点一直往下深入，知道没有路了，返回。我们的栈实质记录的是我们深度优先遍历的路径 我们从A点开始遍历： 1、A进栈，Stack[A] **打印A**。弹出A，当前弹出的节点A去枚举它的后代BCD，B没加入过栈中。压入A再压入B,Stack[B,A]。**打印B** 2、弹出B,B的直接后代邻居为CE,C再栈中而E不在栈中。重新压B,压E，Stack[E,B,A]。**打印E** 3、弹出E,E有邻居D,D不在栈中。压回E，再压D,此时Stack[D,E,B,A]。**打印D** 4、 弹出D,D的直接邻居是A,A已经在栈中了。说明A-B-E-D这条路径走到了尽头。弹出D之后，当前循环结束。继续while栈不为空，重复操作 ```Java package class10; import java.util.HashSet; import java.util.Stack; public class Code02_DFS { public static void dfs(Node node) { if (node == null) { return; } Stack stack = new Stack<>(); // Set的作用和宽度优先遍历类似，保证重复的点不要进栈 HashSet set = new HashSet<>(); stack.add(node); set.add(node); // 打印实时机是在进栈的时候 // 同理该步可以换成其他处理逻辑，表示深度遍历处理某件事情 System.out.println(node.value); while (!stack.isEmpty()) { Node cur = stack.pop(); // 枚举当前弹出节点的后代 for (Node next : cur.nexts) { // 只要某个后代没进入过栈，进栈 if (!set.contains(next)) { // 把该节点的父亲节点重新压回栈中 stack.push(cur); // 再把自己压入栈中 stack.push(next); set.add(next); // 打印当前节点的值 System.out.println(next.value); // 直接break，此时栈顶是当前next节点，达到深度优先的目的 break; } } } } } ```

1.2.4 图的拓扑排序

1、在图中找到所有入度为0的点输出 2、把所有入度为0的点在图中删掉，切消除这些点的影响边。继续找入度为0的点输出，删除，消边，周而复始 3、图的所有点都被删除后，依次输出的顺序就是图的拓扑排序 **要求：有向图且其中没有环** **应用：事件安排，编译顺序** > 在我们的项目中，项目之间互相依赖，就是拓扑排序的一个应用，从最底层依赖的包往上层编译，最终把总的项目编译通过。所以项目中循环依赖是编译不通过的 例如下列的有向无环图： ``` graph LR; A-->B B-->C A-->C C-->E E-->F C-->T F-->T ``` 图中的字母代表事情，做事情的先后顺序就是按照有向图的描述，请安排事情的先后顺序（拓扑排序）。 拓扑排序为：A B C E F T ```Java package class10; import java.util.ArrayList; import java.util.HashMap; import java.util.LinkedList; import java.util.List; import java.util.Queue; public class Code03_TopologySort { // 有向无环图，返回拓扑排序的顺序list public static List sortedTopology(Graph graph) { // key：某一个node // value：该节点剩余的入度 HashMap inMap = new HashMap<>(); // 剩余入度为0的点，才能进这个队列 Queue zeroInQueue = new LinkedList<>(); // 拿到该图中所有的点集 for (Node node : graph.nodes.values()) { // 初始化每个点，每个点的入度是原始节点的入度信息 // 加入inMap inMap.put(node, node.in); // 由于是有向无环图，则必定有入度为0的起始点。放入到zeroInQueue if (node.in == 0) { zeroInQueue.add(node); } } // 拓扑排序的结果，依次加入result List result = new ArrayList<>(); while (!zeroInQueue.isEmpty()) { // 该有向无环图初始入度为0的点，直接弹出放入结果集中 Node cur = zeroInQueue.poll(); result.add(cur); // 该节点的下一层邻居节点，入度减一且加入到入度的map中 for (Node next : cur.nexts) { inMap.put(next, inMap.get(next) - 1); // 如果下一层存在入度变为0的节点，加入到0入度的队列中 if (inMap.get(next) == 0) { zeroInQueue.add(next); } } } return result; } } ```

1.2.5 图的最小生成树算法

> 最小生成树解释，就是在不破坏原有图点与点的连通性基础上，让连通的边的整体权值最小。返回最小权值或者边的集合

1.2.5.1 Kruskal（克鲁斯卡尔）算法

> 连通性借助并查集实现 1、总是从权值最小的边开始考虑，依次考察权值依次变大的边 2、当前的边要么进入最小生成树的集合，要么丢弃 3、如果当前的边进入最小生成树的集合中不会形成环，就要当前边 4、如果当前的边进入最小生成树的集合中会形成环，就不要当前边 5、考察完所有边之后，最小生成树的集合也就得到了 ```Java package class10; import java.util.Collection; import java.util.Comparator; import java.util.HashMap; import java.util.HashSet; import java.util.PriorityQueue; import java.util.Set; import java.util.Stack; //undirected graph only public class Code04_Kruskal { // Union-Find Set 我们的并查集结构 public static class UnionFind { // key 某一个节点， value key节点往上的节点 private HashMap fatherMap; // key 某一个集合的代表节点, value key所在集合的节点个数 private HashMap sizeMap; public UnionFind() { fatherMap = new HashMap(); sizeMap = new HashMap(); } public void makeSets(Collection nodes) { fatherMap.clear(); sizeMap.clear(); for (Node node : nodes) { fatherMap.put(node, node); sizeMap.put(node, 1); } } private Node findFather(Node n) { Stack path = new Stack<>(); while(n != fatherMap.get(n)) { path.add(n); n = fatherMap.get(n); } while(!path.isEmpty()) { fatherMap.put(path.pop(), n); } return n; } public boolean isSameSet(Node a, Node b) { return findFather(a) == findFather(b); } public void union(Node a, Node b) { if (a == null || b == null) { return; } Node aDai = findFather(a); Node bDai = findFather(b); if (aDai != bDai) { int aSetSize = sizeMap.get(aDai); int bSetSize = sizeMap.get(bDai); if (aSetSize <= bSetSize) { fatherMap.put(aDai, bDai); sizeMap.put(bDai, aSetSize + bSetSize); sizeMap.remove(aDai); } else { fatherMap.put(bDai, aDai); sizeMap.put(aDai, aSetSize + bSetSize); sizeMap.remove(bDai); } } } } public static class EdgeComparator implements Comparator { @Override public int compare(Edge o1, Edge o2) { return o1.weight - o2.weight; } } // K算法 public static Set kruskalMST(Graph graph) { // 先拿到并查集结构 UnionFind unionFind = new UnionFind(); // 该图的所有点加入到并查集结构 unionFind.makeSets(graph.nodes.values()); // 边按照权值从小到大排序，加入到堆 PriorityQueue priorityQueue = new PriorityQueue<>(new EdgeComparator()); for (Edge edge : graph.edges) { // M 条边 priorityQueue.add(edge); // O(logM) } Set result = new HashSet<>(); // 堆不为空，弹出小根堆的堆顶 while (!priorityQueue.isEmpty()) { // 假设M条边，O(logM) Edge edge = priorityQueue.poll(); // 如果该边的左右两侧不在同一个集合中 if (!unionFind.isSameSet(edge.from, edge.to)) { // O(1) // 要这条边 result.add(edge); // 联合from和to unionFind.union(edge.from, edge.to); } } return result; } } ``` > K算法求无向图的最小生成树，求权值是没问题的，如果纠结最小生成树的连通结构，实质是少了一侧，即A指向B, B指向A只会保留其一。可以手动补齐

1.2.5.2 Prim算法

> P算法无需并查集结构，普通set即可满足 1、任意指定一个出发点，譬如A, A的直接边被解锁 2、在A解锁的边里选择一个最小的边，该边两侧有没有新节点，如果有选择该边。没有就舍弃该边 3、在被选择的新节点中再解锁该节点的直接边 4、周而复始，直到所有点被解锁 ```Java package class10; import java.util.Comparator; import java.util.HashSet; import java.util.PriorityQueue; import java.util.Set; // undirected graph only public class Code05_Prim { public static class EdgeComparator implements Comparator { @Override public int compare(Edge o1, Edge o2) { return o1.weight - o2.weight; } } public static Set primMST(Graph graph) { // 解锁的边进入小根堆 PriorityQueue priorityQueue = new PriorityQueue<>(new EdgeComparator()); // 哪些点被解锁出来了 HashSet nodeSet = new HashSet<>(); // 已经考虑过的边，不要重复考虑 Set result = new HashSet<>(); // 依次挑选的的边在result里 Set result = new HashSet<>(); // 随便挑了一个点,进入循环处理完后直接break for (Node node : graph.nodes.values()) { // node 是开始点 if (!nodeSet.contains(node)) { // 开始节点保留 nodeSet.add(node); // 开始节点的所有邻居节点全部放到小根堆 // 即由一个点，解锁所有相连的边 for (Edge edge : node.edges) { if (!edgeSet.contains(edge)) { edgeSet.add(edge); priorityQueue.add(edge); } } while (!priorityQueue.isEmpty()) { // 弹出解锁的边中，最小的边 Edge edge = priorityQueue.poll(); // 可能的一个新的点,from已经被考虑了，只需要看to Node toNode = edge.to; // 不含有的时候，就是新的点 if (!nodeSet.contains(toNode)) { nodeSet.add(toNode); result.add(edge); for (Edge nextEdge : toNode.edges) { // 没加过的，放入小根堆 if (!edgeSet.contains(edge)) { edgeSet.add(edge); priorityQueue.add(edge); } } } } } // 直接break意味着我们不用考虑森林的情况 // 如果不加break我们可以兼容多个无向图的森林的生成树 // break; } return result; } // 请保证graph是连通图 // graph[i][j]表示点i到点j的距离，如果是系统最大值代表无路 // 返回值是最小连通图的路径之和 public static int prim(int[][] graph) { int size = graph.length; int[] distances = new int[size]; boolean[] visit = new boolean[size]; visit[0] = true; for (int i = 0; i < size; i++) { distances[i] = graph[0][i]; } int sum = 0; for (int i = 1; i < size; i++) { int minPath = Integer.MAX_VALUE; int minIndex = -1; for (int j = 0; j < size; j++) { if (!visit[j] && distances[j] < minPath) { minPath = distances[j]; minIndex = j; } } if (minIndex == -1) { return sum; } visit[minIndex] = true; sum += minPath; for (int j = 0; j < size; j++) { if (!visit[j] && distances[j] > graph[minIndex][j]) { distances[j] = graph[minIndex][j]; } } } return sum; } public static void main(String[] args) { System.out.println("hello world!"); } } ```

1.2.6 图的最短路径算法

1.2.6.1 Dijkstra(迪杰特斯拉)算法

> Dijkstra算法必须要求边的权值不为负，且必须指定出发点。则可以求出发点到所有节点的最短距离是多少。如果到达不了，为正无穷 1、Dijkstra算法必须指定一个源点 2、生成一个源点到各个点的最小距离表，一开始只有一条记录，即原点到自己的最小距离为0，源点到其他所有点的最小距离都未正无穷大 3、从距离表中拿出没拿过记录里的最小记录，通过这个点出发的边，更新源点到各个点的最小距离表，不断重复这一步 4、源点到所有的点记录如果都被拿过一遍，过程停止，最小距离表得到了 ```Java package class10; import java.util.HashMap; import java.util.HashSet; import java.util.Map.Entry; // 没改进之前的版本 public class Code06_Dijkstra { // 返回的map表就是从from到表中key的各个的最小距离 // 某个点不在map中记录，则from到该点位正无穷 public static HashMap dijkstra1(Node from) { // 从from出发到所有点的最小距离表 HashMap distanceMap = new HashMap<>(); // from到from距离为0 distanceMap.put(from, 0); // 已经求过距离的节点，存在selectedNodes中，以后再也不碰 HashSet selectedNodes = new HashSet<>(); // from 0 得到没选择过的点的最小距离 Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes); // 得到minNode之后 while (minNode != null) { // 把minNode对应的距离取出,此时minNode就是桥连点 int distance = distanceMap.get(minNode); // 把minNode上所有的邻边拿出来 // 这里就是要拿到例如A到C和A到桥连点B再到C哪个距离小的距离 for (Edge edge : minNode.edges) { // 某条边对应的下一跳节点toNode Node toNode = edge.to; // 如果关于from的distencMap中没有去toNode的记录，表示正无穷，直接添加该条 if (!distanceMap.containsKey(toNode)) { // from到minNode的距离加上个minNode到当前to节点的边距离 distanceMap.put(toNode, distance + edge.weight); // 如果有，看该距离是否更小，更小就更新 } else { distanceMap.put(edge.to, Math.min(distanceMap.get(toNode), distance + edge.weight)); } } // 锁上minNode，表示from通过minNode到其他节点的最小值已经找到 // minNode将不再使用 selectedNodes.add(minNode); // 再在没有选择的节点中挑选MinNode当成from的桥接点 minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes); } // 最终distanceMap全部更新，返回 return distanceMap; } // 得到没选择过的点的最小距离 public static Node getMinDistanceAndUnselectedNode( HashMap distanceMap, HashSet touchedNodes) { Node minNode = null; int minDistance = Integer.MAX_VALUE; for (Entry entry : distanceMap.entrySet()) { Node node = entry.getKey(); int distance = entry.getValue(); // 没有被选择过，且距离最小 if (!touchedNodes.contains(node) && distance < minDistance) { minNode = node; minDistance = distance; } } return minNode; } /** * 我们可以借助小根堆来替代之前的distanceMap。达到优化算法的目的 * 原因是之前我们要遍历hash表选出最小距离，现在直接是堆顶元素 * 但是我们找到通过桥节点更小的距离后，需要临时更该堆结构中元素数据 * 所以系统提供的堆我们需要改写 **/ public static class NodeRecord { public Node node; public int distance; public NodeRecord(Node node, int distance) { this.node = node; this.distance = distance; } } // 自定义小根堆结构 // 需要提供add元素的方法，和update元素的方法 // 需要提供ignore方法，表示我们已经找到from到某节点的最短路径 // 再出现from到该节点的其他路径距离，我们直接忽略 public static class NodeHeap { private Node[] nodes; // 实际的堆结构 // key 某一个node， value 上面堆中的位置 // 如果节点曾经进过堆，现在不在堆上，则node对应-1 // 用来找需要ignore的节点 private HashMap heapIndexMap; // key 某一个节点， value 从源节点出发到该节点的目前最小距离 private HashMap distanceMap; private int size; // 堆上有多少个点 public NodeHeap(int size) { nodes = new Node[size]; heapIndexMap = new HashMap<>(); distanceMap = new HashMap<>(); size = 0; } // 该堆是否空 public boolean isEmpty() { return size == 0; } // 有一个点叫node，现在发现了一个从源节点出发到达node的距离为distance // 判断要不要更新，如果需要的话，就更新 public void addOrUpdateOrIgnore(Node node, int distance) { // 如果该节点在堆上，就看是否需要更新 if (inHeap(node)) { distanceMap.put(node, Math.min(distanceMap.get(node), distance)); // 该节点进堆，判断是否需要调整 insertHeapify(node, heapIndexMap.get(node)); } // 如果没有进入过堆。新建，进堆 if (!isEntered(node)) { nodes[size] = node; heapIndexMap.put(node, size); distanceMap.put(node, distance); insertHeapify(node, size++); } // 如果不在堆上，且进来过堆上，什么也不做，ignore } // 弹出from到堆顶节点的元素，获取到该元素的最小距离，再调整堆结构 public NodeRecord pop() { NodeRecord nodeRecord = new NodeRecord(nodes[0], distanceMap.get(nodes[0])); // 把最后一个元素放在堆顶，进行heapify swap(0, size - 1); heapIndexMap.put(nodes[size - 1], -1); distanceMap.remove(nodes[size - 1]); // free C++同学还要把原本堆顶节点析构，对java同学不必 nodes[size - 1] = null; heapify(0, --size); return nodeRecord; } private void insertHeapify(Node node, int index) { while (distanceMap.get(nodes[index]) < distanceMap.get(nodes[(index - 1) / 2])) { swap(index, (index - 1) / 2); index = (index - 1) / 2; } } private void heapify(int index, int size) { int left = index * 2 + 1; while (left < size) { int smallest = left + 1 < size && distanceMap.get(nodes[left + 1]) < distanceMap.get(nodes[left]) ? left + 1 : left; smallest = distanceMap.get(nodes[smallest]) < distanceMap.get(nodes[index]) ? smallest : index; if (smallest == index) { break; } swap(smallest, index); index = smallest; left = index * 2 + 1; } } // 判断node是否进来过堆 private boolean isEntered(Node node) { return heapIndexMap.containsKey(node); } // 判断某个节点是否在堆上 private boolean inHeap(Node node) { return isEntered(node) && heapIndexMap.get(node) != -1; } private void swap(int index1, int index2) { heapIndexMap.put(nodes[index1], index2); heapIndexMap.put(nodes[index2], index1); Node tmp = nodes[index1]; nodes[index1] = nodes[index2]; nodes[index2] = tmp; } } // 使用自定义小根堆，改进后的dijkstra算法 // 从from出发，所有from能到达的节点，生成到达每个节点的最小路径记录并返回 public static HashMap dijkstra2(Node from, int size) { // 申请堆 NodeHeap nodeHeap = new NodeHeap(size); // 在堆上添加from节点到from节点距离为0 nodeHeap.addOrUpdateOrIgnore(from, 0); // 最终的结果集 HashMap result = new HashMap<>(); while (!nodeHeap.isEmpty()) { // 每次在小根堆弹出堆顶元素 NodeRecord record = nodeHeap.pop(); // 拿出的节点 Node cur = record.node; // from到该节点的距离 int distance = record.distance; // 以此为桥接点，找是否有更小的距离到该节点的其他to节点 // addOrUpdateOrIgnore该方法保证如果from到to的节点没有，就add // 如果有,看是否需要Ignore，如果不需要Ignore且更小，就Update for (Edge edge : cur.edges) { nodeHeap.addOrUpdateOrIgnore(edge.to, edge.weight + distance); } result.put(cur, distance); } return result; } } ```

1.2.6.2 floyd算法

> 图节点的最短路径，处理权值可能为负的情况。三层for循环，比较简单