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;



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;

    
    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 < entry.getValue().size(); i++) {
   System.out.print(entry.getValue().get(i).name + " " + "距离是： " + entry.getKey().distonext.get(i) + ", ");
 }
 System.out.println();
      }
    }


    
    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 n = adjaNode.get(node); // 获取到源点的边集
      
      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 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 (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);

    // 下面尝试一下非连通图

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

}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持考高分网。