[자료구조 & 알고리즘] 11. 다익스트라

다익스트라

1. 가중치 그래프 (Weighted Graph)

• 그래프의 간선에 가중치가 부여된 그래프.

• 각 정점을 방문할 때 모든 간선이 똑같은 비용이 드는 것이 아닌, 서로 다른 비용이 드는 것을 나타낼 때 사용.

     - 예를 들어, 도시들과 그들을 잇는 도로를 그래프로 표현할 때 각 도시들끼리 도로를 따라 이동할 때 걸리는 시간을 가중치로 나타낼 수 있음.

• 구현 방법

     - 인접 행렬

          - 각 정점에서 연결되지 않은 정점에는 0, 연결된 정점에는 가중치를 표현

private static int[][] adjacencyMatrix() {
    return new int[][] {
            {0, 2, 0, 1, 0, 0, 0, 0},
            {0, 0, 1, 0, 9, 6, 0, 0},
            {0, 0, 0, 0, 0, 4, 0, 0},
            {0, 0, 3, 0, 0, 0, 5, 0},
            {0, 0, 0, 0, 0, 0, 0, 1},
            {0, 0, 0, 0, 3, 0, 0, 0},
            {0, 0, 0, 0, 0, 7, 0, 9},
            {0, 0, 0, 0, 0, 0, 0, 0}
    };
}

 

     - 인접 리스트

          - 연결된 정점만 표현하는 것이 아닌 배열을 이용하여 가중치도 같이 저장

private static List<List<int[]>> adjacencyList() {
    List<List<int[]>> weightedGraph = new ArrayList<>();
    weightedGraph.add(List.of(new int[] {1, 2}, new int[] {3, 1}));
    weightedGraph.add(List.of(new int[] {2, 1}, new int[] {4, 9}, new int[] {5, 6}));
    weightedGraph.add(List.of(new int[] {5, 4}));
    weightedGraph.add(List.of(new int[] {2, 3}, new int[] {6, 5}));
    weightedGraph.add(List.of(new int[] {7, 1}));
    weightedGraph.add(List.of(new int[] {4, 3}));
    weightedGraph.add(List.of(new int[] {5, 7}, new int[] {7, 9}));
    weightedGraph.add(List.of());
    return weightedGraph;
}

 

2. 다익스트라 (Dijkstra)

• 가중치 그래프에서 시작점과 도착점이 주어졌을 때, 최단 경로(Shortest Path)를 return하는 알고리즘.

• 방문할 수 있는 노드 중에 가장 비용이 적은 곳을 우선순위로 방문

• 우선순위 큐를 통해 구현

     - 가중치 그래프가 인접 행렬로 표현되어 있을 시 다익스트라 구현 방법

private static int dijkstraForAdjMatrix(int[][] graph, int startVertex, int endVertex) {
    int[] visitedVertex = new int[graph.length];
    Arrays.fill(visitedVertex, -1);
    PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
    priorityQueue.add(new int[] {startVertex, 0});
    while(!priorityQueue.isEmpty()) {
        int[] currentVertexAndWeight = priorityQueue.poll();
        int currentVertex = currentVertexAndWeight[0];
        int currentWeight = currentVertexAndWeight[1];
        if(visitedVertex[currentVertex] == -1) {
            visitedVertex[currentVertex] = currentWeight;
            int[] currentEdges = graph[currentVertex];
            for (int nextVertex = 0; nextVertex < currentEdges.length; nextVertex++) {
                if (currentEdges[nextVertex] != 0) {
                    int nextWeight = currentWeight + currentEdges[nextVertex];
                    priorityQueue.add(new int[]{nextVertex, nextWeight});
                }
            }
        }
    }
    return visitedVertex[endVertex];
}

 

     - 가중치 그래프가 인접 리스트로 표현되어 있을 시 다익스트라 구현 방법

 

private static int dijkstraForAdjList(List<List<int[]>> graph, int startVertex, int endVertex) {
    int[] visitedVertex = new int[graph.size()];
    Arrays.fill(visitedVertex, -1);
    PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
    priorityQueue.add(new int[] {startVertex, 0});
    while(!priorityQueue.isEmpty()) {
        int[] currentVertexAndWeight = priorityQueue.poll();
        int currentVertex = currentVertexAndWeight[0];
        int currentWeight = currentVertexAndWeight[1];
        if(visitedVertex[currentVertex] == -1) {
            visitedVertex[currentVertex] = currentWeight;
            List<int[]> currentEdges = graph.get(currentVertex);
            for (int[] nextEdge : currentEdges) {
                int nextVertex = nextEdge[0];
                int nextWeight = nextEdge[1] + currentWeight;
                priorityQueue.add(new int[]{nextVertex, nextWeight});
            }
        }
    }
    return visitedVertex[endVertex];
}