湛蓝之海 发表于 2021-10-5 18:29:04

java实现单源最短路径

这篇文章主要为大家详细介绍了java实现单源最短路径,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
本文采用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; // 初始化距离数组
      int i;
      /*
       * 对最短路径进行初始化, 设置源点到其他地方的值为无穷大
       * */
      for (i = 0; i < minpath.length; i++) {
      minpath = 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 = 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 == float.max_value) {
            minpath = distance + node.distonext.get(i); // 源点到下一点的距离
          }else if (distance + node.distonext.get(i) < minpath ) { //源点到该顶点的距离变小了, 则改变
            minpath = distance + node.distonext.get(i); // 更新源点到下一个点的距离
          }
      }
      }
      /*
       * 这个for 用于找到 距离集合中 距离源点最近 且并未被访问过的
       * 这个for 同时可以确保 该节点确实可到达
       * */

      for (i = 1; i < minpath.length; i++) {
      if (!nodes.get(i).visited) {
          if (min> minpath ) {
            min = minpath;
            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;
}

}
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持CodeAE代码之家。
原文链接:https://blog.csdn.net/qq_40860649/article/details/81291681

http://www.zzvips.com/article/175508.html
页: [1]
查看完整版本: java实现单源最短路径