当前位置: 首页 > 编程笔记 >

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

后阳炎
2023-03-14
本文向大家介绍java实现最短路径算法之Dijkstra算法,包括了java实现最短路径算法之Dijkstra算法的使用技巧和注意事项,需要的朋友参考一下

前言

Dijkstra算法是最短路径算法中为人熟知的一种,是单起点全路径算法。该算法被称为是“贪心算法”的成功典范。本文接下来将尝试以最通俗的语言来介绍这个伟大的算法,并赋予java实现代码。

一、知识准备:

1、表示图的数据结构

用于存储图的数据结构有多种,本算法中笔者使用的是邻接矩阵。

图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵)存储图中的边或弧的信息。

设图G有n个顶点,则邻接矩阵是一个n*n的方阵,定义为:

从上面可以看出,无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即从矩阵的左上角到右下角的主对角线为轴,右上角的元和左下角相对应的元全都是相等的。

从这个矩阵中,很容易知道图中的信息。

(1)要判断任意两顶点是否有边无边就很容易了;

(2)要知道某个顶点的度,其实就是这个顶点vi在邻接矩阵中第i行或(第i列)的元素之和;

(3)求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍,arc[i][j]为1就是邻接点;

而有向图讲究入度和出度,顶点vi的入度为1,正好是第i列各数之和。顶点vi的出度为2,即第i行的各数之和。

有向图的定义也类似,故不做赘述。

2、单起点全路径

所谓单起点全路径,就是指在一个图中,从一个起点出发,到所有节点的最短路径。 

3、图论的基本知识(读者需自行寻找相关资料)

4、互补松弛条件

设标量d1,d2,....,dN满足

dj<=di + aij,  (i,j)属于A,

且P是以i1为起点ik为终点的路,如果

dj = di + aij, 对P的所有边(i, j)

成立,那么P是从i1到ik的最短路。其中,满足上面两式的被称为最短路问题的互补松弛条件。

二、算法思想

1、令G = (V,E)为一个带权无向图。G中若有两个相邻的节点,i和j。aij(在这及其后面都表示为下标,请注意)为节点i到节点j的权值,在本算法可以理解为距离。每个节点都有一个值di(节点标记)表示其从起点到它的某条路的距离。

2、算法初始有一个数组V用于储存未访问节点的列表,我们暂称为候选列表。选定节点1为起始节点。开始时,节点1的d1=0, 其他节点di=无穷大,V为所有节点。
初始化条件后,然后开始迭代算法,直到V为空集时停止。具体迭代步骤如下:

将d值最小的节点di从候选列表中移除。(本例中V的数据结构采用的是优先队列实现最小值出列,最好使用斐波那契对,在以前文章有过介绍,性能有大幅提示)。对于以该节点为起点的每一条边,不包括移除V的节点, (i, j)属于A, 若dj > di + aij(违反松弛条件),则令

dj = di + aij    , (如果j已经从V中移除过,说明其最小距离已经计算出,不参与此次计算)

可以看到在算法的运算工程中,节点的d值是单调不增的

具体算法图解如下

  

三、java代码实现

public class Vertex implements Comparable<Vertex>{

  /**
   * 节点名称(A,B,C,D)
   */
  private String name;
  
  /**
   * 最短路径长度
   */
  private int path;
  
  /**
   * 节点是否已经出列(是否已经处理完毕)
   */
  private boolean isMarked;
  
  public Vertex(String name){
    this.name = name;
    this.path = Integer.MAX_VALUE; //初始设置为无穷大
    this.setMarked(false);
  }
  
  public Vertex(String name, int path){
    this.name = name;
    this.path = path;
    this.setMarked(false);
  }
  
  @Override
  public int compareTo(Vertex o) {
    return o.path > path?-1:1;
  }
}

public class Graph {

  /*
   * 顶点
   */
  private List<Vertex> vertexs;

  /*
   * 边
   */
  private int[][] edges;

  /*
   * 没有访问的顶点
   */
  private Queue<Vertex> unVisited;

  public Graph(List<Vertex> vertexs, int[][] edges) {
    this.vertexs = vertexs;
    this.edges = edges;
    initUnVisited();
  }
  
  /*
   * 搜索各顶点最短路径
   */
  public void search(){
    while(!unVisited.isEmpty()){
      Vertex vertex = unVisited.element();
      //顶点已经计算出最短路径,设置为"已访问"
       vertex.setMarked(true);  
      //获取所有"未访问"的邻居
        List<Vertex> neighbors = getNeighbors(vertex);  
      //更新邻居的最短路径
      updatesDistance(vertex, neighbors);    
      pop();
    }
    System.out.println("search over");
  }
  
  /*
   * 更新所有邻居的最短路径
   */
  private void updatesDistance(Vertex vertex, List<Vertex> neighbors){
    for(Vertex neighbor: neighbors){
      updateDistance(vertex, neighbor);
    }
  }
  
  /*
   * 更新邻居的最短路径
   */
  private void updateDistance(Vertex vertex, Vertex neighbor){
    int distance = getDistance(vertex, neighbor) + vertex.getPath();
    if(distance < neighbor.getPath()){
      neighbor.setPath(distance);
    }
  }

  /*
   * 初始化未访问顶点集合
   */
  private void initUnVisited() {
    unVisited = new PriorityQueue<Vertex>();
    for (Vertex v : vertexs) {
      unVisited.add(v);
    }
  }

  /*
   * 从未访问顶点集合中删除已找到最短路径的节点
   */
  private void pop() {
    unVisited.poll();
  }

  /*
   * 获取顶点到目标顶点的距离
   */
  private int getDistance(Vertex source, Vertex destination) {
    int sourceIndex = vertexs.indexOf(source);
    int destIndex = vertexs.indexOf(destination);
    return edges[sourceIndex][destIndex];
  }

  /*
   * 获取顶点所有(未访问的)邻居
   */
  private List<Vertex> getNeighbors(Vertex v) {
    List<Vertex> neighbors = new ArrayList<Vertex>();
    int position = vertexs.indexOf(v);
    Vertex neighbor = null;
    int distance;
    for (int i = 0; i < vertexs.size(); i++) {
      if (i == position) {
        //顶点本身,跳过
        continue;
      }
      distance = edges[position][i];  //到所有顶点的距离
      if (distance < Integer.MAX_VALUE) {
        //是邻居(有路径可达)
        neighbor = getVertex(i);
        if (!neighbor.isMarked()) {
          //如果邻居没有访问过,则加入list;
          neighbors.add(neighbor);
        }
      }
    }
    return neighbors;
  }

  /*
   * 根据顶点位置获取顶点
   */
  private Vertex getVertex(int index) {
    return vertexs.get(index);
  }

  /*
   * 打印图
   */
  public void printGraph() {
    int verNums = vertexs.size();
    for (int row = 0; row < verNums; row++) {
      for (int col = 0; col < verNums; col++) {
        if(Integer.MAX_VALUE == edges[row][col]){
          System.out.print("X");
          System.out.print(" ");
          continue;
        }
        System.out.print(edges[row][col]);
        System.out.print(" ");
      }
      System.out.println();
    }
  }
}

public class Test {

  public static void main(String[] args){
    List<Vertex> vertexs = new ArrayList<Vertex>();
    Vertex a = new Vertex("A", 0);
    Vertex b = new Vertex("B");
    Vertex c = new Vertex("C");
    Vertex d = new Vertex("D");
    Vertex e = new Vertex("E");
    Vertex f = new Vertex("F");
    vertexs.add(a);
    vertexs.add(b);
    vertexs.add(c);
    vertexs.add(d);
    vertexs.add(e);
    vertexs.add(f);
    int[][] edges = {
        {Integer.MAX_VALUE,6,3,Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE},
        {6,Integer.MAX_VALUE,2,5,Integer.MAX_VALUE,Integer.MAX_VALUE},
        {3,2,Integer.MAX_VALUE,3,4,Integer.MAX_VALUE},
        {Integer.MAX_VALUE,5,3,Integer.MAX_VALUE,5,3},
        {Integer.MAX_VALUE,Integer.MAX_VALUE,4,5,Integer.MAX_VALUE,5},
        {Integer.MAX_VALUE,Integer.MAX_VALUE,Integer.MAX_VALUE,3,5,Integer.MAX_VALUE}
    
    };
    Graph graph = new Graph(vertexs, edges);
    graph.printGraph();
    graph.search();
  }
  
}

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

 类似资料:
  • 本文向大家介绍java实现Dijkstra最短路径算法,包括了java实现Dijkstra最短路径算法的使用技巧和注意事项,需要的朋友参考一下 任务描述:在一个无向图中,获取起始节点到所有其他节点的最短路径描述 Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。 Dijkstra一般的表述

  • 本文向大家介绍java实现dijkstra最短路径寻路算法,包括了java实现dijkstra最短路径寻路算法的使用技巧和注意事项,需要的朋友参考一下 【引用】迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径。  它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止。 基本思想 通过Dijkstra计算图G中的最短路径时,需要指

  • 我已经从Cormen的第三版参考“算法介绍”中找到的伪代码中实现了Dijkstra算法,用于单源最短路径问题。 我的实现是在python上使用链接列表在邻接列表表示中表示图形。这意味着节点列表是一个链接列表,每个节点都有一个链接列表来表示每个节点的边缘。此外,我没有实现或使用任何二进制堆或斐波那契堆作为算法所需的最小优先级队列,因此当过程需要提取与源距离最小的下一个节点时,我在节点链表内搜索O(V

  • 本文向大家介绍python实现Dijkstra算法的最短路径问题,包括了python实现Dijkstra算法的最短路径问题的使用技巧和注意事项,需要的朋友参考一下 迪杰斯特拉(Dijkstra)算法主要是针对没有负值的有向图,求解其中的单一起点到其他顶点的最短路径算法。 1 算法原理 迪杰斯特拉(Dijkstra)算法是一个按照路径长度递增的次序产生的最短路径算法。下图为带权值的有向图,作为程序中

  • 本文向大家介绍Dijkstra算法最短路径的C++实现与输出路径,包括了Dijkstra算法最短路径的C++实现与输出路径的使用技巧和注意事项,需要的朋友参考一下 某个源点到其余各顶点的最短路径 这个算法最开始心里怕怕的,不知道为什么,花了好长时间弄懂了,也写了一遍,又遇到时还是出错了,今天再次写它,心里没那么怕了,耐心研究,懂了之后会好开心的,哈哈 Dijkstra算法: 图G 如图:若要求从顶

  • 最短路径问题的Dijkstra算法 是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯彻算法使用了广度优先搜索解决非负权有向图的单源最短路径问题,算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。 这个算法的python实现途径很多,网上能够发现不少。这里推荐一个我在网上看到的,本来打算自己写,看了这个,决定自己不写了,因为他的已经太好了。 解决(Python) #