다익스트라

다익스트라

• 정점의 가중치나 간선의 가중치가 있는 그래프에서 최단 경로를 찾을 때

BFS

• 가중치가 없는 그래프에서 최단 경로를 찾거나, 특정 레벨의 모든 노드를 탐색할 때

인접행렬

• 노드 수가 적고 간선이 많은 밀집 그래프에 적합하다.
• 간선 존재 여부를 빠르게 확인해야 할 때 유용하다.

인접리스트

• 노드 수가 많고 간선이 적은 희소 그래프에 적합하다.
• 인접 노드를 빠르게 순회해야 할 때 유용하다.

	Time Complexity
인접 행렬	O((V^2)logV)
인접 리스트	O((V+E)logV)

1. 가장 작은 가중치로 갈 수 있는 정점을 선택한다. → Greedy
2. 해당 정점을 이미 방문했다면 continue;
3. 해당 정점을 최초로 방문한다.
4. 해당 정점 방문 표시
5. 최초 방문은 제일 작은 가중치로 방문한 것이므로 distances에 넣기
6. 해당 정점에서 갈 수 있는 인접 정점들을 우선순위 큐에 추가 → DP

public static long[] dijkstra(ArrayList<ArrayList<Edge>> graph, int startVertex) {

    long[] distances = new long[graph.size()];
    boolean[] visited = new boolean[graph.size()];
    PriorityQueue<Vertex> pQ = new PriorityQueue<>(new Comparator<Vertex>() {
        @Override
        public int compare(Vertex o1, Vertex o2) {
            if (o1.weight < o2.weight)
                return -1;
            else if (o1.weight == o2.weight)
                return 0;
            else
                return 1;
        }
    });

    for (int i = 1; i < graph.size(); i++)
        distances[i] = Long.MAX_VALUE;

    pQ.add(new Vertex(startVertex, 0));

    while (!pQ.isEmpty()) {
        Vertex curVertex = pQ.remove();

        if (visited[curVertex.number])
            continue;

        visited[curVertex.number] = true;
        distances[curVertex.number] = curVertex.weight;

        for (int i = 0; i < graph.get(curVertex.number).size(); i++) {
            Edge curEdge = graph.get(curVertex.number).get(i);

            pQ.add(new Vertex(curEdge.endVertex, curVertex.weight + curEdge.weight));
        }
    }

    return distances;
}