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;  }}