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 nodes = new ArrayList<>(); // 表示图顶点 ， 同时他也作为V集合 private Map> adjaNode = new HashMap<>(); // 表示图的边 private ArrayList 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 node = new ArrayList(); 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> entry : adjaNode.entrySet()) { System.out.println("顶点 ： " + entry.getKey().name + " 链接顶点有： "); for(int i = 0; i (); // 存储已经遍历过的点 minPath = new float[nodes.size()]; // 初始化距离数组 int i; /* * 对最短路径进行初始化， 设置源点到其他地方的值为无穷大 * */ for (i = 0; i  n = adjaNode.get(node); // 获取到源点的边集 /* * 先对源节点进行初始化 * 1. 对 距离数组进行初始化。 * 2. 找到源点到某个距离最短的点， 并标记 * * */ for (i = 0; i  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 n = adjaNode.get(node); // 获得边集 for (i = 0 ; i  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 distonext = new ArrayList<>(); //这一点 到另外每一个点的距离 public Node1(int id, String name) { this.id = id; this.name = name; } }