Algorithm | Dijkstra Algorithm

Dijkstra Algorithm ?

 다익스트라 알고리즘(Dijkstra Algorithm)은 가중치를 가진 그래프에서 최단 경로를 탐색하는 알고리즘이다. 단, 가중치가 양수일 경우에만 사용이 가능하다.

 

 다익스트라 알고리즘의 기본 로직은 출발 정점을 기준으로 연결되어 있는 정점들을 추가해가며 최단 거리를 갱신해나간다. 이러한 방식으로 출발 정점에서부터 다른 모든 정점까지의 최단 경로를 구할 수 있다. 그 과정은 다음과 같다.

 

1. 출발 정점으로부터 각 정점에 도달하는데까지 걸리는 시간을 계산한다. (연결이 되지 않았다면 가중치는 ∞)

2. 방문하지 않은 정점 중에서 제일 짧은 시간이 걸리는 정점을 찾는다.

3. 찾아낸 정점에서 이웃 정점에 도달하는데 걸리는 시간을 계산한다. 만약  이전에 기록한 시간보다 적게 걸린다면 정보를 수정한다.

4. 2 - 3번을 반복하여 최종 목적지까지의 최단 거리를 찾는다.

 

다익스트라 알고리즘 구현(in JAVA)

package graph;

public class WeightGraph {
  private int[][] graph;  // 간선 가중치 정보 저장
  
  public WeightGraph(int v) {
    graph = new int[v+1][v+1];
  }

  public void add(int from, int to, int w) {
    graph[from][to] = w;
  }

  public void dijkstra(int start) {
    boolean[] visit = new boolean[graph.length]; // 방문 여부 저장
    int[] distance = new int[graph.length];  // 정점 최단거리 저장

    for (int i = 1; i < distance.length; i++) { 
      if(i != start) distance[i] = Integer.MAX_VALUE; // 시작점을 제외한 모든 노드의 거리를 infinity로 변경
    }
    visit[start] = true;  // 시작점은 방문한 것으로 변경

    for (int i = 1; i < distance.length; i++) {
      if(graph[start][i] > 0) {  // 시작 정점과 연결되어있다면
        distance[i] = graph[start][i]; // 거리값 갱신
      }
    }

    for (int j = 1; j < distance.length; j++) { // 모든 정점에 대해 반복문 수행
      int min_index = 0;
      int min = Integer.MAX_VALUE;
      // 방문하지 않은 정점들 중 가장 최단거리 찾기
      for (int i = 1; i < distance.length; i++) {
        if(!visit[i] && distance[i] < min) {
          min_index = i;
          min = distance[i];
        }
      }
  
      visit[min_index] = true;  // 최단거리를 가진 정점 방문
  
      for (int i = 1; i < distance.length; i++) {
        if(graph[min_index][i] > 0) { // 방문한 정점과 이웃한 정점 찾기
          int d = min + graph[min_index][i];  // 방문한 정점을 거쳐 이웃한 정점을 갔을 때의 거리
          if(distance[i] > d) distance[i] = d;  // 만약 기록된 거리보다 작다면 거리 갱신
        }
      }

    }

    // 정점 순서대로 최단거리 출력
    for (int i = 1; i < distance.length; i++) {
      if(distance[i] == Integer.MAX_VALUE) System.out.println("Infinity");
      else System.out.println(distance[i]);
    }

  }

}

 위에 설명한 과정에 따라 인접행렬로 구현된 그래프에서 다익스트라 알고리즘을 구현해보았다.

---

Reference

 

· 네비게이션 길찾기 : 다익스트라 알고리즘 - 개념편 -https://www.youtube.com/watch?v=qaiuC3Q73-M

· 다익스트라 알고리즘 - https://hsp1116.tistory.com/42

· [도서] Hello Coding 그림으로 개념을 이해하는 알고리즘