Dijkstra Implementation

July 24, 2023

Dijkstra Implementation

Dijkstra 구현 설명

가중치가 있는 그래프에서, 특정한 한 정점에서 다른 모든 정점까지의 최단 거리를 구하는 문제
음의 가중치가 있는 경우 사용 불가하지만, 유향 그래프에서는 사용 가능
아래 코드는 무향 연결 그래프이며, 그래프가 2d array 형태로 주어진 경우
0번 부터 N - 1번 까지의 노드가 존재
smallestNode 함수와 dijkstra 함수로 구성
smallestNode 함수
- 방문하지 않은 노드 중 시작 점에서 가장 가까운 노드를 방문하는 함수
- 모든 노드가 방문된 경우 -1을 반환
dijkstra 함수: 다음과 같은 알고리즘을 따름
1. 각 노드 i에 대해 출발 노드로부터의 최소 거리를 distance[i]에 저장
  - 출발 노드는 이 거리가 0임
  - 나머지 노드들은 무한대로 초기화
2. ``smallestIdx함수를 통해curNode`노드를 선택하고, 방문했다고 표시
  - 최초에는 출발 노드가 선택됨
3. curNode 기준으로 인접하지만 방문되지 않은 노드 i 들에 대해 다음을 수행
  - distance[curNode] + weights[curNode][i]를 계산
  - 이 값이 distance[i]보다 작다면, 현재 i로 가는 경로보다 curNode를 거쳐 i로 가는 길이 더 짧다는 뜻
  - 이 경우, distance[i] = distance[curNode] + weights[curNode][i]로 업데이트 하면 됨
4. 모든 노드를 방문할 때 까지 2 - 3번 반복

구현

// Input
public static int N = read();
public static int[][] weights = readGraph();

public static int smallestNode(int[] arr, boolean[] visited) {
    int node = -1;
    int smallest = Integer.MAX_VALUE;
    for (int i = 0; i < N; i++) {
        if (!visited[i] && arr[i] < smallest) {
            smallest = arr[i];
            node = i;
        }
    }
    return node;
}

public static int[] dijkstra(int start) {
    int[] distance = new int[N];
    boolean[] visited = new boolean[N];

    for (int i = 0; i < N; i++) {
        distance[i] = Integer.MAX_VALUE;
    }
    distance[start] = 0;

    int curNode;
    // While visit every node
    while ((curNode = smallestIdx(distance, visited)) != -1) {
        visited[curNode] = true;
        for (int i = 0; i < N; i++) {
            if (visited[i]) {
                continue;
            }
            int curDistance = distance[curNode] + weights[curNode][i];
            if (curDistance < distance[i]) {
                distance[i] = curDistance;
            }
        }
    }
    return distance;
}

Dijkstra Implementation

Dijkstra 구현 설명

구현

References