天马网络 网站建设,织梦大气蓝色门户资讯网站模板,网站建设营销,wordpress 生成cookie戳蓝字“CSDN云计算”关注我们哦#xff01;技术头条#xff1a;干货、简洁、多维全面。更多云计算精华知识尽在眼前#xff0c;get要点、solve难题#xff0c;统统不在话下#xff01;作者#xff1a;蠢萌的小灰转自#xff1a;程序员小灰————— 第二天 ————… 戳蓝字“CSDN云计算”关注我们哦技术头条干货、简洁、多维全面。更多云计算精华知识尽在眼前get要点、solve难题统统不在话下作者蠢萌的小灰转自程序员小灰————— 第二天 —————如何遍历呢第一层遍历顶点A第二层遍历A的邻接顶点B和C第三层遍历顶点B的邻接顶点D、E遍历顶点C的邻接顶点F第四层遍历顶点E的邻接顶点G也就是目标节点由此得出图中顶点A到G的第一条最短路径是A-B-E-G换句话说就是寻找从A到G之间权值之和最小的路径。————————————究竟什么是迪杰斯特拉算法它是如何寻找图中顶点的最短路径呢这个算法的本质是不断刷新起点与其他各个顶点之间的 “距离表”。让我们来演示一下迪杰斯特拉的详细过程第1步创建距离表。表中的Key是顶点名称Value是从起点A到对应顶点的已知最短距离。但是一开始我们并不知道A到其他顶点的最短距离是多少Value默认是无限大第2步遍历起点A找到起点A的邻接顶点B和C。从A到B的距离是5从A到C的距离是2。把这一信息刷新到距离表当中第3步从距离表中找到从A出发距离最短的点也就是顶点C。第4步遍历顶点C找到顶点C的邻接顶点D和FA已经遍历过不需要考虑。从C到D的距离是6所以A到D的距离是268从C到F的距离是8所以从A到F的距离是2810。把这一信息刷新到表中接下来重复第3步、第4步所做的操作第5步也就是第3步的重复从距离表中找到从A出发距离最短的点C已经遍历过不需要考虑也就是顶点B。第6步也就是第4步的重复遍历顶点B找到顶点B的邻接顶点D和EA已经遍历过不需要考虑。从B到D的距离是1所以A到D的距离是516小于距离表中的8从B到E的距离是6所以从A到E的距离是5611。把这一信息刷新到表中在第6步A到D的距离从8刷新到6可以看出距离表所发挥的作用。距离表通过迭代刷新用新路径长度取代旧路径长度最终可以得到从起点到其他顶点的最短距离第7步从距离表中找到从A出发距离最短的点B和C不用考虑也就是顶点D。第8步遍历顶点D找到顶点D的邻接顶点E和F。从D到E的距离是1所以A到E的距离是617小于距离表中的11从D到F的距离是2所以从A到F的距离是628小于距离表中的10。把这一信息刷新到表中第9步从距离表中找到从A出发距离最短的点也就是顶点E。第10步遍历顶点E找到顶点E的邻接顶点G。从E到G的距离是7所以A到G的距离是7714。把这一信息刷新到表中第11步从距离表中找到从A出发距离最短的点也就是顶点F。第10步遍历顶点F找到顶点F的邻接顶点G。从F到G的距离是3所以A到G的距离是8311小于距离表中的14。把这一信息刷新到表中就这样除终点以外的全部顶点都已经遍历完毕距离表中存储的是从起点A到所有顶点的最短距离。显然从A到G的最短距离是11。路径A-B-D-F-G按照上面的思路我们来看一下代码实现/** * Dijkstra最短路径算法 */public static MapInteger, Integer dijkstra(Graph graph, int startIndex) { //创建距离表存储从起点到每一个顶点的临时距离 MapInteger, Integer distanceMap new HashMapInteger,Integer(); //记录遍历过的顶点 SetInteger accessedSet new HashSetInteger (); //图的顶点数量 int size graph.vertexes.length; //初始化最短路径表到达每个顶点的路径代价默认为无穷大 for(int i1; isize; i){ distanceMap.put(i, Integer.MAX_VALUE); } //遍历起点刷新距离表 accessedSet.add(0); ListEdge edgesFromStart graph.adj[startIndex]; for(Edge edge : edgesFromStart) { distanceMap.put(edge.index, edge.weight); } //主循环重复 遍历最短距离顶点和刷新距离表 的操作 for(int i1; isize; i) { //寻找最短距离顶点 int minDistanceFromStart Integer.MAX_VALUE; int minDistanceIndex -1; for(int j1; jsize; j) { if(!accessedSet.contains(j) distanceMap.get(j) minDistanceFromStart) { minDistanceFromStart distanceMap.get(j); minDistanceIndex j; } } if(minDistanceIndex -1){ break; } //遍历顶点刷新距离表 accessedSet.add(minDistanceIndex); for(Edge edge : graph.adj[minDistanceIndex]) { if(accessedSet.contains(edge.index)){ continue; } int weight edge.weight; int preDistance distanceMap.get(edge.index); if(weight ! Integer.MAX_VALUE (minDistanceFromStart weight preDistance)) { distanceMap.put(edge.index, minDistanceFromStart weight); } } } return distanceMap;}public static void main(String[] args) { Graph graph new Graph(7); initGraph(graph); MapInteger, Integer distanceMap dijkstra(graph, 0); int distance distanceMap.get(6); System.out.println(distance);}/** * 图的顶点 */private static class Vertex { String data; Vertex(String data) { this.data data; }}/** * 图的边 */private static class Edge { int index; int weight; Edge(int index, int weight) { this.index index; this.weight weight; }}/** * 图 */private static class Graph { private Vertex[] vertexes; private LinkedListEdge adj[]; Graph(int size){ //初始化顶点和邻接矩阵 vertexes new Vertex[size]; adj new LinkedList[size]; for(int i0; iadj.length; i){ adj[i] new LinkedListEdge(); } }}private static void initGraph(Graph graph){ graph.vertexes[0] new Vertex(A); graph.vertexes[1] new Vertex(B); graph.vertexes[2] new Vertex(C); graph.vertexes[3] new Vertex(D); graph.vertexes[4] new Vertex(E); graph.vertexes[5] new Vertex(F); graph.vertexes[6] new Vertex(G); graph.adj[0].add(new Edge(1, 5)); graph.adj[0].add(new Edge(2, 2)); graph.adj[1].add(new Edge(0, 5)); graph.adj[1].add(new Edge(3, 1)); graph.adj[1].add(new Edge(4, 6)); graph.adj[2].add(new Edge(0, 2)); graph.adj[2].add(new Edge(3, 6)); graph.adj[2].add(new Edge(5, 8)); graph.adj[3].add(new Edge(1, 1)); graph.adj[3].add(new Edge(2, 6)); graph.adj[3].add(new Edge(4, 1)); graph.adj[3].add(new Edge(5, 2)); graph.adj[4].add(new Edge(1, 6)); graph.adj[4].add(new Edge(3, 1)); graph.adj[4].add(new Edge(6, 7)); graph.adj[5].add(new Edge(2, 8)); graph.adj[5].add(new Edge(3, 2)); graph.adj[5].add(new Edge(6, 3)); graph.adj[6].add(new Edge(4, 7)); graph.adj[6].add(new Edge(5, 3));}福利扫描添加小编微信备注“姓名公司职位”加入【云计算学习交流群】和志同道合的朋友们共同打卡学习推荐阅读为什么给黑洞拍照需要这么长时间V神玩起freestyle! 5位以太坊核心大咖在悉尼的演讲精华全在这了| 直击EDCON“重构”黑洞26岁MIT研究生的新算法 | 人物志零编程基础的 15 岁少年仅用 9 个月开发了 9 款 App京东“地震”程序员 996 再上热搜黑名单增至 84 家真香朕在看了
