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

}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • java实现dijkstra最短路径寻路算法

    [引用]迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径. 它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止. 基本思想 通过Dijkstra计算图G中的最短路径时,需要指定起点s(即从顶点s开始计算). 此外,引进两个集合S和U.S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度),而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离). 初始时,S中只有起点s:U中是除s之外的顶点,并且U中顶点的路径是

  • java实现Dijkstra最短路径算法

    任务描述:在一个无向图中,获取起始节点到所有其他节点的最短路径描述 Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止. Dijkstra一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN, CLOSE表方式 用OPEN,CLOSE表的方式,其采用的是贪心法的算法策略,大概过程如下: 1.声明两个集合,open和close,open用于存储未遍历的节点,close用来存储

  • java实现最短路径算法之Dijkstra算法

    前言 Dijkstra算法是最短路径算法中为人熟知的一种,是单起点全路径算法.该算法被称为是"贪心算法"的成功典范.本文接下来将尝试以最通俗的语言来介绍这个伟大的算法,并赋予java实现代码. 一.知识准备: 1.表示图的数据结构 用于存储图的数据结构有多种,本算法中笔者使用的是邻接矩阵. 图的邻接矩阵存储方式是用两个数组来表示图.一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵)存储图中的边或弧的信息. 设图G有n个顶点,则邻接矩阵是一个n*n的方阵,定义为: 从上面可以看出,无

  • Java实现Dijkstra输出最短路径的实例

    Java实现Dijkstra输出指定起点到终点的最短路径 前言: 最近在公司参加了一个比赛,其中涉及的一个问题,可以简化成如是描述:一个二维矩阵,每个点都有权重,需要找出从指定起点到终点的最短路径. 马上就想到了Dijkstra算法,所以又重新温故了一遍,这里给出Java的实现. 而输出最短路径的时候,在网上也进行了查阅,没发现什么标准的方法,于是在下面的实现中,我给出了一种能够想到的比较精简的方式:利用prev[]数组进行递归输出. package graph.dijsktra; import

  • Java实现Floyd算法求最短路径

    本文实例为大家分享了Java实现Floyd算法求最短路径的具体代码,供大家参考,具体内容如下 import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class TestMainIO { /** * @param args * @throws FileNotFoundException */ public static void main(Stri

  • Java实现利用广度优先遍历(BFS)计算最短路径的方法

    本文实例讲述了Java实现利用广度优先遍历(BFS)计算最短路径的方法.分享给大家供大家参考.具体分析如下: 我们用字符串代表图的顶点(vertax),来模拟学校中Classroom, Square, Toilet, Canteen, South Gate, North Gate几个地点,然后计算任意两点之间的最短路径. 如下图所示: 如,我想从North Gate去Canteen, 程序的输出结果应为: BFS: From [North Gate] to [Canteen]: North Ga

  • java使用Dijkstra算法实现单源最短路径

    单源最短路径问题,即在图中求出给定顶点到其它任一顶点的最短路径.在弄清楚如何求算单源最短路径问题之前,必须弄清楚最短路径的最优子结构性质. 一.最短路径的最优子结构性质 该性质描述为:如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,k和s是这条路径上的中间顶点,那么P(k,s)必定是从k到s的最短路径.下面证明该性质的正确性. 假设P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,则有P(i,j)=P(i,k)+P(k,s)+P(s,

  • 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最短路径算法是一种单源最短路径 *

  • C++计算任意权值的单源最短路径(Bellman-Ford)

    本文实例为大家分享了C++计算任意权值单源最短路径的具体代码,供大家参考,具体内容如下 一.有Dijkstra算法求最短路径了,为什么还要用Bellman-Ford算法 Dijkstra算法不适合用于带有负权值的有向图. 如下图: 用Dijkstra算法求顶点0到各个顶点的最短路径: (1)首先,把顶点0添加到已访问顶点集合S中,选取权值最小的邻边<0, 2>,权值为5 记录顶点2的最短路径为:dist[2]=5, path[2]=0,把顶点2添加到集合S中. 顶点2,没有邻边(从顶点2出发,

  • Java集合框架源码分析之LinkedHashMap详解

    LinkedHashMap简介 LinkedHashMap是HashMap的子类,与HashMap有着同样的存储结构,但它加入了一个双向链表的头结点,将所有put到LinkedHashmap的节点一一串成了一个双向循环链表,因此它保留了节点插入的顺序,可以使节点的输出顺序与输入顺序相同. LinkedHashMap可以用来实现LRU算法(这会在下面的源码中进行分析). LinkedHashMap同样是非线程安全的,只在单线程环境下使用. LinkedHashMap源码剖析 LinkedHashM

  • Java实现单链表翻转实例代码

    Java实现单链表反转,递归和非递归两种形式 /** * 反转单链表 */ /** * 定义链表 * * @author 16026 * */ class Node { int val; Node next; public Node(int val) { this.val = val; } } public class ReverseList { /** * 反转链表 * * @param head * @return */ public static Node reverseList(Node

  • java 实现单链表逆转详解及实例代码

    java 实现单链表逆转详解 实例代码: class Node { Node next; String name; public Node(String name) { this.name = name; } /** * 打印结点 */ public void show() { Node temp = this; do { System.out.print(temp + "->"); temp = temp.next; }while(temp != null); System.o

  • 基于HTML5+js+Java实现单文件文件上传到服务器功能

    上传单文件到服务器       应公司要求,在HTML5页面上实现上传文件到服务器,对于一个还没毕业的实习生菜鸟来说,这可不得了-----不会,网上各种百度,找各种博客还是没解决,最后还是请教了公司的大神,人家给卸了一个例子,然后根据人家写的终于把这个上传文件搞定. 好了,开始上代码. HTML5代码: <form name="upform" action="" method="POST"> <input type ="

  • java 中Buffer源码的分析

    java 中Buffer源码的分析 Buffer Buffer的类图如下: 除了Boolean,其他基本数据类型都有对应的Buffer,但是只有ByteBuffer才能和Channel交互.只有ByteBuffer才能产生Direct的buffer,其他数据类型的Buffer只能产生Heap类型的Buffer.ByteBuffer可以产生其他数据类型的视图Buffer,如果ByteBuffer本身是Direct的,则产生的各视图Buffer也是Direct的. Direct和Heap类型Buff

  • java 数据结构单链表的实现

    java 数据结构单链表的实现 单链表实现链表的打印及元素删除操作,链表的实现主要是next属性的定义,将一堆节点关联起来的.实现简单的链表如下: public class LinkNode { private int value; private LinkNode next; public LinkNode(int x) { value = x; } public LinkNode getNext(){ return next; } public void setNext(LinkNode n

  • C++实现多源最短路径之Floyd算法示例

    本文实例讲述了C++实现多源最短路径之Floyd算法.分享给大家供大家参考,具体如下: #include<cstdio> #include<cstring> #include<iostream> #define MAX 999 using namespace std; int n,m; int e[MAX][MAX]; void Init() { for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) { if(i==

随机推荐