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;

   }

}