当前位置: 主页 > JAVA语言

java实现最短路径算法-Dijkstra算法:单起点全路径算法——Dijkstra矩阵

发布时间:2023-06-15 22:10   浏览次数:次   作者:佚名

前言

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

一、知识准备:

1、表示图的数据结构

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

新浪短链接算法实现_java实现最短路径算法_漏桶算法 java实现

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

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

java实现最短路径算法_漏桶算法 java实现_新浪短链接算法实现

新浪短链接算法实现_漏桶算法 java实现_java实现最短路径算法

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

java实现最短路径算法_新浪短链接算法实现_漏桶算法 java实现

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

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

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

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

而有向图讲究入度和出度,顶点vi的入度为1,正好是第i列各数之和。顶点vi的出度为2java实现最短路径算法,即第i行的各数之和。

新浪短链接算法实现_漏桶算法 java实现_java实现最短路径算法

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

2、单起点全路径

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

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

4、互补松弛条件

新浪短链接算法实现_java实现最短路径算法_漏桶算法 java实现

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

dj di + aij(违反松弛条件),则令

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

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

具体算法图解如下

新浪短链接算法实现_漏桶算法 java实现_java实现最短路径算法

java实现最短路径算法_漏桶算法 java实现_新浪短链接算法实现

新浪短链接算法实现_java实现最短路径算法_漏桶算法 java实现

三、java代码实现

public class Vertex implements Comparable{
  /**
   * 节点名称(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 vertexs;
  /*
   * 边
   */
  private int[][] edges;
  /*
   * 没有访问的顶点
   */
  private Queue unVisited;
  public Graph(List vertexs, int[][] edges) {
    this.vertexs = vertexs;
    this.edges = edges;
    initUnVisited();
  }
  
  /*
   * 搜索各顶点最短路径
   */
  public void search(){
    while(!unVisited.isEmpty()){
      Vertex vertex = unVisited.element();
      //顶点已经计算出最短路径,设置为"已访问"
       vertex.setMarked(true);  
      //获取所有"未访问"的邻居
        List neighbors = getNeighbors(vertex);  
      //更新邻居的最短路径
      updatesDistance(vertex, neighbors);    
      pop();
    }
    System.out.println("search over");
  }
  
  /*
   * 更新所有邻居的最短路径
   */
  private void updatesDistance(Vertex vertex, List 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();
    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 getNeighbors(Vertex v) {
    List neighbors = new ArrayList();
    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 vertexs = new ArrayList();
    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();
  }
  
}