[Algorithm] 다익스트라(Dijkstra) 알고리즘

설명

• 하나의 정점에서 다른 모든 정점으로의 최단경로들을 구하는 알고리즘
• 참고
  • https://m.blog.naver.com/ndb796/221234424646

예시

• 그래프

• 1부터 탐색 시작
• 기준 노드(1)의 거리값을 0으로 초기화, 기준 노드를 큐에 추가
• 큐가 빌 때까지 아래 과정 반복
• 큐에서 기준 노드(1)를 하나 꺼내 방문했다고 표시
• 기준 노드(1)에서 방문한 적 없는 인접 노드(2, 4)들 중 큐에 들어간 적 없는 노드들을 큐에 추가
  • 큐 : 2, 4
• 인접 노드(2, 4)들까지의 거리값을 누적해 작은 거리값을 해당 노드의 거리값으로 지정
  • 거리값 : 2(2), 4(1)
• 위 과정 반복

코드

public class Node {
    public int value;
    public boolean isVisited; // 방문한 적 있는지 판단값
    public boolean isEnqueue; // 큐에 들어간 적 있는지 판단값
    public int distance = Integer.MAX_VALUE; // 해당 노드까지의 거리값
    public List<Edge> edgeList = new ArrayList<>(); // 인접 간선 목록
    public List<Node> path = new ArrayList<>(); // 해당 노드까지의 노드 목록

    public Node(int value) {
        this.value = value;
    }
}

public class Edge {
    public Node node1;
    public Node node2;
    public int distance;

    public Edge(Node node1, Node node2, int distance) {
        this.node1 = node1;
        this.node2 = node2;
        this.distance = distance;
    }
}

public class Graph {
    private Map<Integer, Node> nodeMap = new HashMap<>();

    public void join(int value1, int value2, int distance) {
        Node node1 = nodeMap.getOrDefault(value1, new Node(value1));
        Node node2 = nodeMap.getOrDefault(value2, new Node(value2));

        Edge edge = new Edge(node1, node2, distance);
        node1.edgeList.add(edge);
        node2.edgeList.add(edge);

        nodeMap.put(value1, node1);
        nodeMap.put(value2, node2);
    }

    public List<Integer> getPath(int start, int end) {
        Node fromNode = nodeMap.get(start);
        fromNode.distance = 0;
        fromNode.isEnqueue = true;
        fromNode.path.add(fromNode);

        Queue<Node> nodeQueue = new LinkedList<>();
        nodeQueue.add(fromNode);

        while (!nodeQueue.isEmpty()) {
            fromNode = nodeQueue.remove();
            fromNode.isVisited = true;

            for (Edge edge : fromNode.edgeList) {
                Node toNode = edge.node1 != fromNode ? edge.node1 : edge.node2;

                if (toNode.isVisited) {
                    continue;
                }

                if (!toNode.isEnqueue) {
                    toNode.isEnqueue = true;
                    nodeQueue.add(toNode);
                }

                int newDistance = fromNode.distance + edge.distance;

                if (toNode.distance > newDistance) {
                    toNode.distance = newDistance;
                    toNode.path.clear();
                    toNode.path.addAll(fromNode.path);
                    toNode.path.add(toNode);
                }
            }
        }

        return nodeMap.get(end).path.stream().map(node -> node.value).collect(Collectors.toList());
    }
}

class SolutionTest extends Specification {
    @Unroll
    def "#graphData, #start, #end -> #result"() {
        expect:
        Graph graph = new Graph()
        graphData.each { values -> graph.join(values.get(0), values.get(1), values.get(2)) }
        graph.getPath(start, end) == result

        where:
        graphData                                                                                           | start | end | result
        [[1, 2, 2], [1, 4, 1], [2, 4, 2], [2, 3, 3], [3, 4, 3], [3, 5, 1], [3, 6, 5], [4, 5, 1], [5, 6, 2]] | 1     | 1   | [1]
        [[1, 2, 2], [1, 4, 1], [2, 4, 2], [2, 3, 3], [3, 4, 3], [3, 5, 1], [3, 6, 5], [4, 5, 1], [5, 6, 2]] | 1     | 2   | [1, 2]
        [[1, 2, 2], [1, 4, 1], [2, 4, 2], [2, 3, 3], [3, 4, 3], [3, 5, 1], [3, 6, 5], [4, 5, 1], [5, 6, 2]] | 1     | 3   | [1, 4, 3]
        [[1, 2, 2], [1, 4, 1], [2, 4, 2], [2, 3, 3], [3, 4, 3], [3, 5, 1], [3, 6, 5], [4, 5, 1], [5, 6, 2]] | 1     | 4   | [1, 4]
        [[1, 2, 2], [1, 4, 1], [2, 4, 2], [2, 3, 3], [3, 4, 3], [3, 5, 1], [3, 6, 5], [4, 5, 1], [5, 6, 2]] | 1     | 5   | [1, 4, 5]
        [[1, 2, 2], [1, 4, 1], [2, 4, 2], [2, 3, 3], [3, 4, 3], [3, 5, 1], [3, 6, 5], [4, 5, 1], [5, 6, 2]] | 1     | 6   | [1, 4, 5, 6]
        [[1, 2, 2], [1, 4, 1], [2, 4, 2], [2, 3, 3], [3, 4, 3], [3, 5, 1], [3, 6, 5], [4, 5, 1], [5, 6, 2]] | 2     | 6   | [2, 4, 5, 6]
        [[1, 2, 2], [1, 4, 1], [2, 4, 2], [2, 3, 3], [3, 4, 3], [3, 5, 1], [3, 6, 5], [4, 5, 1], [5, 6, 2]] | 4     | 6   | [4, 5, 6]
    }
}