java实现单源最短路径
程序员文章站
2024-03-01 14:08:16
本文采用java实现单源最短路径,并带有略微详细的注解,供大家参考,具体内容如下
package com.qf.greaph;
import java.ut...
本文采用java实现单源最短路径,并带有略微详细的注解,供大家参考,具体内容如下
package com.qf.greaph; import java.util.arraylist; import java.util.arrays; import java.util.hashmap; import java.util.map; import java.util.map.entry; /** * @author jiayoo * 7 / 30 * dijkstra最短路径算法是一种单源最短路径 * 本文采用的是邻接表表示图。 * * 图的表示: 1. 采用 arraylist 来储存 图的顶点 * 2. 采用 map 来储存 边集 , map 可以 实现 一对多的关系, 因此能很好的实现邻接表结构 * 3. 采用arraylist的原因 是使 边集有序 这样, node 的里面 那个记录距离的集合才能一一对应 */ public class minpath { private static class graph{ private arraylist<node1> nodes = new arraylist<>(); // 表示图顶点 , 同时他也作为v集合 private map<node1, arraylist<node1>> adjanode = new hashmap<>(); // 表示图的边 private arraylist<node1> nodes1 ; // 表示s集合, 即存储已经访问的节点, private float[] minpath; //用来存储源点到每个顶点的距离 float min = float.max_value; /** * @param start * @param end * @param distance * 构建邻接表。使之成为图 */ public void addadjanode(node1 start, node1 end, float distance) { if (!nodes.contains(start)) { nodes.add(start); } if (!nodes.contains(end)) { nodes.add(end); } if (adjanode.containskey(start) && adjanode.get(start).contains(end)) { return ; } if (adjanode.containskey(start)) { adjanode.get(start).add(end); }else { arraylist<node1> node = new arraylist<node1>(); node.add(end); adjanode.put(start, node); } start.distonext.add(distance); } /** * 将图打印出来 */ public void pringraph() { if (nodes == null || adjanode == null) { system.out.println("图为空"); return ; } for (entry<node1, arraylist<node1>> entry : adjanode.entryset()) { system.out.println("顶点 : " + entry.getkey().name + " 链接顶点有: "); for(int i = 0; i < entry.getvalue().size(); i++) { system.out.print(entry.getvalue().get(i).name + " " + "距离是: " + entry.getkey().distonext.get(i) + ", "); } system.out.println(); } } /** * 1.这个方法用于初始化s集合 及 初始化距离数组 * 2. 设置源点, 并且将源点作为内容 初始化算法 */ public void findminpath() { node1 node1 = null; // 用来记录列表里最小的点 nodes1 = new arraylist<>(); // 存储已经遍历过的点 minpath = new float[nodes.size()]; // 初始化距离数组 int i; /* * 对最短路径进行初始化, 设置源点到其他地方的值为无穷大 * */ for (i = 0; i < minpath.length; i++) { minpath[i] = float.max_value; } node1 node = nodes.get(0); nodes1.add(node); // 将源点加入 s 集合 node.visited = true; arraylist<node1> n = adjanode.get(node); // 获取到源点的边集 /* * 先对源节点进行初始化 * 1. 对 距离数组进行初始化。 * 2. 找到源点到某个距离最短的点, 并标记 * * */ for (i = 0; i < n.size(); i++) { minpath[n.get(i).id] = node.distonext.get(i); // 最短路径记录 if (min > node.distonext.get(i)) { min = node.distonext.get(i); node1 = n.get(i); // 找到当前最短路径 } } this.process(node1, min); } private void process(node1 node, float distance ) { min = float.max_value; //作为标记 node1 node1 = null; // 同样记录距离最短的点 int i; arraylist<node1> n = adjanode.get(node); // 获得边集 for (i = 0 ; i < n.size(); i++) { if (!n.get(i).visited) { // 这个边集里的顶点不在 s 集合里 if (minpath[n.get(i).id] == float.max_value) { minpath[n.get(i).id] = distance + node.distonext.get(i); // 源点到下一点的距离 }else if (distance + node.distonext.get(i) < minpath[n.get(i).id] ) { //源点到该顶点的距离变小了, 则改变 minpath[n.get(i).id] = distance + node.distonext.get(i); // 更新源点到下一个点的距离 } } } /* * 这个for 用于找到 距离集合中 距离源点最近 且并未被访问过的 * 这个for 同时可以确保 该节点确实可到达 * */ for (i = 1; i < minpath.length; i++) { if (!nodes.get(i).visited) { if (min > minpath[i] ) { min = minpath[i]; node1 = nodes.get(i); } } } if (node1 != null) { node1.visited = true; process(node1, min); //源点到 当前的距离 }else { // 说明此位置没有后续节点, 或者 已经全部被访问完了, 则到达此位置只需要加上此位置的值 } } } public static void main(string[] args) { node1 n1 = new node1(0,"a"); node1 n2 = new node1(1,"b"); node1 n3 = new node1(2,"c"); node1 n4 = new node1(3,"d"); node1 n5 = new node1(4,"e"); node1 n6 = new node1(5,"f"); graph gp = new graph(); gp.addadjanode(n1, n2, 6); gp.addadjanode(n2, n1, 6); gp.addadjanode(n1, n3, 3); gp.addadjanode(n3, n1, 3); gp.addadjanode(n2, n3, 2); gp.addadjanode(n3, n2, 2); gp.addadjanode(n2, n4, 5); gp.addadjanode(n4, n2, 5); gp.addadjanode(n3, n4, 3); gp.addadjanode(n4, n3, 3); gp.addadjanode(n3, n5, 4); gp.addadjanode(n5, n3, 4); gp.addadjanode(n4, n5, 2); gp.addadjanode(n5, n4, 2); gp.addadjanode(n4, n6, 3); gp.addadjanode(n6, n4, 3); gp.addadjanode(n5, n6, 5); gp.addadjanode(n6, n5, 5); // 下面尝试一下非连通图 // /** // * 权值: 1 // * a -----------b // * 权 | * // * 值 | * 权值: 3 // * 2 | * // * c-----d // * 权值: 5 // * // * // * */ // // gp.addadjanode(n1, n2, 1); // gp.addadjanode(n2, n1, 1); // // gp.addadjanode(n1, n3, 2); // gp.addadjanode(n3, n1, 2); // // gp.addadjanode(n1, n4, 3); // gp.addadjanode(n4, n1, 3); // // gp.addadjanode(n3, n4, 5); // gp.addadjanode(n4, n3, 5); gp.pringraph(); system.out.println("--------------------------------------------------------------------"); system.out.println("此数组下标代表id,值代表从源点分别到各点的最短距离, a开始的下标是0, b、c、d等依次类推, 并且源点默认设置为id为零0的开始"); gp.findminpath(); system.out.println(arrays.tostring(gp.minpath)); } } /** * 顶点类 */ class node1{ string name; boolean visited = false; // 访问状态。有效 减少原算法移除v集合中元素所花费的时间 int id = -1; // 设置默认id为-1 arraylist<float> distonext = new arraylist<>(); //这一点 到另外每一个点的距离 public node1(int id, string name) { this.id = id; this.name = name; } }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。