Java에서 최단 경로 알고리즘을 위한 Dijkstra 알고리즘 구현

이 글에서는 주로 Java에서 최단 경로 알고리즘을 구현한 Dijkstra 알고리즘을 소개합니다. Dijkstra 알고리즘은 단일 시작 전체 경로 알고리즘입니다.

머리말

Dijkstra의 알고리즘은 잘 알려진 최단 경로 알고리즘이며 단일 시작 전체 경로 알고리즘입니다. 이 알고리즘은 '탐욕 알고리즘'의 성공적인 사례라고 불린다. 이 기사에서는 가장 널리 사용되는 언어로 이 훌륭한 알고리즘을 소개하고 Java 구현 코드를 제공하려고 합니다.

1. 지식 준비:

1. 그래프를 나타내는 데이터 구조

이 알고리즘에서는 저자가 인접 행렬을 사용합니다.

그래프의 인접 행렬 저장 방법은 두 개의 배열을 사용하여 그래프를 표현하는 것입니다. 1차원 배열은 그래프에 정점 정보를 저장하고, 2차원 배열(인접 행렬)은 그래프에 모서리 또는 호 정보를 저장합니다.

그래프 G에 n개의 정점이 있다고 가정하면 인접 행렬은 다음과 같이 정의되는 n*n 정사각형 행렬입니다.

위에서 볼 수 있듯이 무향 그래프의 가장자리 배열은 대칭 행렬입니다. 소위 대칭 행렬은 n차 행렬의 요소가 aij = aji를 충족한다는 것을 의미합니다. 즉, 행렬의 왼쪽 위 모서리부터 오른쪽 아래 모서리까지의 주대각선이 축이고, 오른쪽 위 모서리에 있는 요소와 왼쪽 아래 모서리에 해당하는 요소가 모두 동일합니다.

이 매트릭스를 통해 사진 속 정보를 쉽게 알 수 있습니다.

(1) 두 정점에 가장자리가 있는지 없는지 확인하는 것은 매우 쉽습니다.

(2) 특정 정점의 차수를 아는 것은 실제로 정점 vi가 i번째 행에 있거나 또는 (i번째 열) 인접 행렬의 요소인 out-degree와 out-degree의 합, 정점 vi의 in-degree는 1이며, 이는 정확히 i번째 열에 있는 숫자의 합입니다. 정점 vi의 진출 차수는 2이며, 이는 i번째 행에 있는 숫자의 합입니다.

유향 그래프의 정의도 비슷하므로 자세한 내용은 다루지 않겠습니다.

2. 단일 시작점 전체 경로

소위 단일 시작점 전체 경로는 시작점에서 시작하여 그래프의 모든 노드까지의 최단 경로를 말합니다.

3. 그래프 이론의 기본 지식(관련 정보는 독자가 직접 찾아야 함)

4. 보완 완화 조건

스칼라 d1, d2,...,dN이 dj88f37d0accf7a6c1432ed884b031e775 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에서 최단 경로 알고리즘을 위한 Dijkstra 알고리즘 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!