1. 최단 거리

그래프의 시작점에서 다른 지점까지의 최단 거리

• 최단 거리를 구하는 알고리즘은 매우 다양함
  • 그 중 2개만 집중적으로 공부!

    → BFS & Dijkstra

    	BFS	Dijkstra
    간선 가중치	1	≥ 0
    시간 복잡도	O(V+E)	O(ElogV)

• BFS 최단 거리는 그래프 탐색에서 자세히

Dijkstra

• input
  • 그래프 (v, e)
    • 간선 가중치 ≥ 0
  • 시작점 s
    • 시작점이 여러 개 있는 multi-source Dijkstra도 존재
• output
  • 시작점에서 모든 점까지의 최단 거리
    • 어차피 모든 점에 대한 최단거리를 구하기 때문에 도착점이 중요하지 않음
• 시간 복잡도
  • O(VlogE)
• 필요한 정보
  • dist[i]
    • 시작점부터 i번 정점까지 최단 거리
  • 자료구조 D → {v, d}
    • 시작점에서 v까지 d만에 갈 수 있음을 확인함

2. 동작 과정

1. dist 배열 초기화 & 자료구조 D에 (start,0) 저장

   • dist[start] = 0
   • 나머지는 무한대(최대값)

2. D에 데이터가 있는 경우

   • (v, d) 중에서 d가 가장 작은 값 꺼냄
   • priority queue를 사용해 정렬해서 d가 가장 작은 값부터 꺼냄

3. dist[v] < d

   • true
     • 이미 최단거리보다 큰 값이므로 가치가 없는 (v, d)
   • false
     • 가치가 있는 데이터 → 4번 과정

4. (v, d)를 통해 새로운 데이터를 D에 저장

   • v가 c만큼 걸려서 갈 수 있는 정점 w
   • d + c < dist[w]
     • dist[w] = d + c
     • (w, d+c) D에 추가

   

5. 자료구조 D가 비어있는지 확인

   • true
     • 탐색 종료
   • false
     • 2번 과정 (반복)

3. 핵심 코드

private static void dijkstra(int startVertex) {
    Queue<Node> queue = new PriorityQueue<>(Comparator.comparingInt(node -> node.distance));

    // initMinDistance
    for (int i = 1; i <= numberOfVertex; i++) {
        minDistance[i] = Integer.MAX_VALUE;

        if (i == startVertex) {
            minDistance[i] = 0;
        }
    }

    queue.add(new Node(startVertex, 0));

    while (!queue.isEmpty()) {
        Node node = queue.poll();
        int nodeNumber = node.number;
        int nodeDistance = node.distance;

        if (nodeDistance > minDistance[nodeNumber]) {
            continue;
        }

        for (Node nextNode : adjacencyList[nodeNumber]) {
            int nextNodeNumber = nextNode.number;
            int newDistance = minDistance[nodeNumber] + nextNode.distance;

            if (newDistance >= minDistance[nextNodeNumber]) {
                continue;
            }

            minDistance[nextNodeNumber] = newDistance;
            queue.add(new Node(nextNodeNumber, newDistance));
        }
    }
}