다익스트라 알고리즘 구현

소개

이번 랩에서는 Java 로 Dijkstra 알고리즘을 구현해 보겠습니다. Dijkstra 알고리즘은 가중 그래프 (weighted graph) 의 최단 경로 문제를 해결하는 데 사용되는 널리 알려진 알고리즘입니다.

Graph 클래스 생성

이 단계에서는 가중 그래프를 나타내는 Graph 라는 클래스를 생성합니다. 그래프의 간선을 나타내기 위해 이 클래스에서 2 차원 인접 행렬 (adjacency matrix) 을 생성합니다.

class Graph
{
    int[][] adjMatrix; // 간선을 나타내는 인접 행렬
    int numOfvertices;

    Graph(int[][] mat, int v)
    {
        this.adjMatrix = mat;
        this.numOfvertices = v;
    }

    void addEdge(int src, int dest, int edgeWeight)
    {
        adjMatrix[src][dest] = edgeWeight;
        adjMatrix[dest][src] = edgeWeight;
    }
}

다익스트라 알고리즘 구현

이 단계에서는 Java 로 Dijkstra 알고리즘을 구현합니다. 방문하지 않은 가장 가까운 노드를 찾기 위해 getClosestVertex 라는 헬퍼 메서드를 생성해 보겠습니다. 또한 dijkstrasShortestPath 메서드에서 메인 알고리즘을 구현합니다. 이 메서드는 Graph 와 소스 정점 (source vertex) 을 매개변수로 받아 최단 거리 배열을 반환합니다.

public static int getClosestVertex(int[] distance, boolean[] visited) {
    int min = Integer.MAX_VALUE;
    int minIdx = -1;
    for(int i=0; i<distance.length; i++) {
        if(distance[i] < min)
            if(visited[i] == false) {
                min = distance[i];
                minIdx = i;
            }
    }
    return minIdx;
}

public static int[] dijkstrasShortestPath(Graph g, int src) {
    // final shortest distance array
    int[] distance = new int[g.numOfvertices];
    // array to tell whether shortest distance of vertex has been found
    boolean[] visited = new boolean[g.numOfvertices];

    // initializing the arrays
    for(int i=0; i<g.numOfvertices; i++) {
        distance[i] = Integer.MAX_VALUE; // initial distance is infinite
        visited[i] = false; // shortest distance for any node has not been found yet
    }
    distance[src] = 0;

    for(int i=0; i<g.numOfvertices; i++) {
        int closestVertex = getClosestVertex(distance, visited); // get the closest node
        if(closestVertex == Integer.MAX_VALUE) // if closest node is infinite distance away, it means that no other node can be reached. So return
            return distance;

        visited[closestVertex] = true;
        for(int j=0; j<g.numOfvertices; j++) {
            if(visited[j] == false) // shortest distance of the node j should not have been finalized
            {
                if(g.adjMatrix[closestVertex][j] != 0) {
                    int d = distance[closestVertex] + g.adjMatrix[closestVertex][j];
                    if(d < distance[j]) // distance via closestVertex is less than the initial distance
                        distance[j] = d;
                }
            }
        }
    }
    return distance;
}

구현 테스트

이 단계에서는 그래프에 간선을 추가하고 dijkstrasShortestPath 메서드를 호출하여 가중 그래프의 소스 정점에서 다른 모든 정점까지의 최단 거리를 찾는 main 메서드를 생성하여 구현을 테스트합니다.

public static void main(String[] args) {
    int numOfVertices = 6;
    int[][] adjMat = new int[6][6];
    Graph graph = new Graph(adjMat, numOfVertices);

    // add edges to the graph
    graph.addEdge(0, 4, 21);
    graph.addEdge(0, 3, 18);
    graph.addEdge(2, 1, 7);
    graph.addEdge(1, 4, 6);
    graph.addEdge(4, 5, 10);
    graph.addEdge(4, 3, 11);
    graph.addEdge(5, 3, 7);

    // call Dijkstra's algorithm to find shortest distance
    int[] dist = dijkstrasShortestPath(graph, 0);
    System.out.print(Arrays.toString(dist));
}

위 코드를 컴파일하고 실행하여 최단 거리 배열 [0, 27, 34, 18, 21, 25]를 얻으십시오.

요약

축하합니다! Dijkstra 알고리즘 구현 랩을 완료했습니다. LabEx 에서 더 많은 랩을 연습하여 실력을 향상시킬 수 있습니다.