Java での最短パス アルゴリズムのためのダイクストラ アルゴリズムの実装

この記事では、Javaで最短経路アルゴリズムを実装するダイクストラアルゴリズムを中心に紹介します。ダイクストラアルゴリズムは、シングルスタートフルパスアルゴリズムです。興味のある方は学習してください。

はじめに ダイクストラのアルゴリズムはよく知られた最短経路アルゴリズムであり、シングルスタートフルパスアルゴリズムです。このアルゴリズムは「貪欲アルゴリズム」の成功例と呼ばれています。この記事では、この優れたアルゴリズムを最も一般的な言語で紹介し、Java 実装コードを提供します。

1. 知識の準備:

1. グラフを表すデータ構造

このアルゴリズムでは、著者は隣接行列を使用します。

グラフの隣接行列の保存方法は、2 つの配列を使用してグラフを表現することです。 1 次元配列にはグラフの頂点情報が格納され、2 次元配列 (隣接行列) にはグラフのエッジまたは円弧の情報が格納されます。

グラフ G に n 個の頂点があると仮定すると、隣接行列は次のように定義される n*n 正方行列になります。

上記からわかるように、無向グラフのエッジ配列は対称行列です。いわゆる対称行列とは、n 次行列の要素が aij = aji を満たすことを意味します。つまり、行列の左上隅から右下隅までの主対角線が軸となり、右上隅の要素と左下隅の対応する要素はすべて等しいということです。

このマトリックスから、画像内の情報を簡単に知ることができます。

(1) 2 つの頂点にエッジがあるかないかを判断するのは非常に簡単です。

(2) 特定の頂点の次数を知るには、実際には頂点 vi が i 番目の行にあるか、または隣接行列の (i 番目の列) 頂点 vi の要素と出力次数の合計、頂点 vi の入次数は 1 であり、これはまさに i 番目の列の数値の合計です。頂点 vi の出次数は 2 で、これは i 番目の行の数値の合計です。

有向グラフの定義も同様なので詳細は割愛します。

2. 単一開始点フルパス

いわゆる単一開始点フルパスとは、グラフ内の開始点からすべてのノードまでの最短パスを指します。

3. グラフ理論の基礎知識 (読者は関連する情報を自分で見つける必要があります)

4. 相補緩和条件

スカラー d1、d2、....、dN が

dj に属し、P は i1 を始点、ik を終点とする道路です。 dj = di + aij の場合、すべての辺 (i, j) P の場合、P これは、i1 から ik への最短経路です。このうち、上の 2 つの式を満たす最短経路問題の相補緩和条件と呼ばれます。

2. アルゴリズムのアイデア

1. G = (V, E) を重み付き無向グラフとする。 G に 2 つの隣接するノードがある場合、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 値が単調に増加しないことがわかります

具体的なアルゴリズム 図は以下の通り

3. 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 での最短パス アルゴリズムのためのダイクストラ アルゴリズムの実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。