Java中關於最短路徑演算法之Dijkstra演算法的實現

這篇文章主要介紹了java實現最短路徑演算法之Dijkstra演算法，　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演算法的實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！