📢본 포스트는 BFS와 다익스트라 알고리즘을 비교하고, 자바 언어로 다익스트라 알고리즘을 비교하는 내용이라
다익스트라 알고리즘의 자세한 과정이 궁금하면 다익스트라 알고리즘(파이썬 버전)을 참고하시기 바랍니다.

📜BFS 알고리즘

먼저 다익스트라 알고리즘을 살펴보기 전에, 가중치가 없는 BFS 알고리즘의 흐름을 살펴보자.
1. 사전세팅: visited 배열과 큐(FIFO구조, 인접 노드 탐색용)로 시작 정점을 삽입한다.

2. 큐가 빌 때까지: 큐를 dequeue해서 현재 노드로 설정하고, for문으로 인접 노드를 탐색한다.
   2.1. 만약 인접 노드를 방문하지 않았으면 -> 방문에 추가 && 큐로 방문 예약

3. 큐가 비었으면(BFS 탐색을 완료했으면) visited를 리턴

📜다익스트라 알고리즘

이 알고리즘은 위의 BFS 알고리즘과 비슷한데, 단지 간선에 비용이 있다는 것과, 비용을 우선순위로 해서 현재까지 알려진 노드의 비용과 비교하면서 최소 비용을 업데이트한다는 것이다.

1. 사전세팅: dist 1차원 배열, 우선순위 큐 초기화
   1.1. dist를 모두 무한대로 설정(아직 경로를 탐색하지 않았다는 의미)
   1.2. 시작 정점을 dist[start] = 0으로 삽입하고, 우선순위 큐에도 삽입한다.
   💡비용을 우선순위로 두기 위해서는,
   implements Comparable<NodeCost>로 인터페이스를 강제로 구현해야 하고,
   public int compareTo(NodeCost other) { return Integer.compare(this.cost, o.cost);를 오버라이딩 해야 한다.
   PriorityQueue<NodeCost> pq = new PriorityQueue<>((node1, node2) -> Integer.compare(node1.cost, node2.cost));와 같이 람다식을 활용하면 커스텀 클래스에서 Comparable 인터페이스를 강제 구현하지 않아도 된다.

2. 큐가 빌 때까지: 큐를 dequeue해서 현재 노드와 현재 비용으로 설정하고, if(curCost > dist[curNode])로 BFS를 통해 우선순위 큐에 추가된 인접노드의 비용이 현재까지 알려진 노드의 비용보다 크면 continue로 아래의 인접 노드 탐색 과정을 스킵한다.
   2.1. for문으로 인접 노드를 탐색
   2.2. 일단 인접 노드의 비용을 현재 비용 + 인접 노드의 비용으로 업데이트한다.
   2.3. 만약 인접 노드의 비용이 기존에 알려진 해당 인접 노드까지의 최단 경로 비용보다 적으면 -> dist에 추가 && 우선순위 큐로 방문 예약
   👉이 과정이 BFS의 중복 방문 체크를 넘어서 "더 짧은 비용 있으면 업데이트" 과정을 동시에 충족한다.

3. 우선순위 큐가 비었으면 dist[end]로 마지막 노드의 비용을 리턴
   👉이때, return dist[end] == Integer.MAX_VALUE ? -1 : dist[end];로 마지막 노드까지 탐색 여부를 알 수 있다.

💻다익스트라

package src.heap;

import java.util.*;

public class Dijkstra {
    public int dijkstra(List<List<NodeCost>> graph, int start, int end) {
        // 최단 거리 저장 배열
        // 1차원 배열(index: node, value: cost)
        int[] dist = new int[graph.size()];
        Arrays.fill(dist, Integer.MAX_VALUE); // 탐색하지 않은 값을 무한대로 초기화
        PriorityQueue<NodeCost> pq = new PriorityQueue<>((node1, node2) -> Integer.compare(node1.cost, node2.cost));
        // 사전 세팅
        dist[start] = 0;
        pq.offer(new NodeCost(start, 0));

        while (!pq.isEmpty()) {
            NodeCost cur = pq.poll();
            int curNode = cur.node;
            int curCost = cur.cost;

            // 우선순위 큐에 추가된 인접노드 비용이 현재까지 알려진 노드의 비용보다 크면 아래의 과정을 스킵
            if (curCost > dist[curNode]) continue;

            // 인접 노드 탐색
            for (NodeCost nextNode : graph.get(curNode)) {
                // 일단 비용 업데이트
                int nextCost = curCost + nextNode.cost;

                // 더 짧은 비용이 있는지 체크
                if (nextCost < dist[nextNode.node]) {
                	// 방문 + 예약
                    dist[nextNode.node] = nextCost;
                    pq.offer(new NodeCost(nextNode.node, nextCost));
                }

            }
        }
		
        // 마지막 노드의 비용을 리턴
        return dist[end] == Integer.MAX_VALUE ? -1 : dist[end];

    }
    
    private static class NodeCost {
        int node;
        int cost;

        public NodeCost(int node, int cost) {
            this.node = node;
            this.cost = cost;

        }
        
    }
    
}

• 만약 문제에서 1~N번 까지의 노드가 주어졌으면, dist의 크기를 graph.size() + 1로 초기화해줘야 한다.
  • 0번 인덱스는 사용하지 않기 때문

📚참고자료
우선순위 큐의 제네릭 타입을 커스텀 클래스로 만드는 방법: https://velog.io/@gillog/Java-Priority-Queue%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%ED%81%90#priority-queue-using-costom-class