Java로 Dijkstra 알고리즘을 이용하여 최단 경로 찾기

Dijkstra Algorithm

음의 가중치가 없는 그래프에서 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘

Java code

public class Dijkstra {
    final static double INFINITY = Double.MAX_VALUE;
 
    public static void main(String[] args) {
        //그래프 저장용 맵
        //HashMap<출발지, HashMap<도착지, 거리>>
        HashMap<String, HashMap<String, Double>> distanceMap = 
                new HashMap<String, HashMap<String, Double>>();
        
        //도착지, 거리 저장용 임시 맵
        //tempMap을 만든후 이를 다시 distanceMap에 put
        HashMap<String, Double> tempMap;
        
        //그래프 입력
        tempMap = new HashMap<>();
        tempMap.put("알롱", 3.0);
        tempMap.put("대롱", 1.0);
        distanceMap.put("본사", tempMap);
        tempMap = new HashMap<>();
        tempMap.put("본사", 3.0);
        tempMap.put("대롱", 0.3);
        tempMap.put("나무", 2.0);
        distanceMap.put("알롱", tempMap);
        tempMap = new HashMap<>();
        tempMap.put("알롱", 2.0);
        tempMap.put("대롱", 1.0);
        distanceMap.put("나무", tempMap);
        tempMap = new HashMap<>();
        tempMap.put("본사", 1.0);
        tempMap.put("나무", 1.0);
        tempMap.put("알롱", 0.3);
        distanceMap.put("대롱", tempMap);
        
        //도착지
        String destination = "알롱";
        
        Result result = dijkstra(distanceMap, "본사");
        double distance = result.distances.get(destination);
        ArrayList<String> stops = new ArrayList<>();
        String curNode = destination;
        stops.add(destination);
        while(!result.preNode.get(curNode).isEmpty()){
            curNode = result.preNode.get(curNode);
            stops.add(curNode);
        }
        
        System.out.println(destination + "까지의 최소 이동 거리: " + distance);
        System.out.println("=====이동 경로=====");
        for(int i = stops.size()-1; i>=0; i--){
            System.out.println(stops.get(i));
        }
        System.out.println("================");
    }
    
    //dijkstra return 오브젝트
    private static class Result{
        //노드 까지 최단 거리
        HashMap<String, Double> distances = new HashMap<>();
        //자기 이전의 노드 -> 루트 추적용
        HashMap<String, String> preNode = new HashMap<>();        
    }
    
    //input: Map<출발지, Map<도착지, 거리>>, 최초 출발지
    //output: Result object
    //do: dijkstra 알고리즘을 이용하여 출발지부터 각 노드까지 최단 거리, 루트 계산
    private static Result dijkstra(HashMap<String, HashMap<String, Double>> graph, String source){
        HashMap<String, Double> distances = new HashMap<>();
        HashMap<String, String> preNode = new HashMap<>();
        
        //출발지의 최단거리는 0, 이전 노드는 없음
        distances.put(source, 0.0);
        preNode.put(source, "");
        
        //그래프의 각 노드를 저장할 집합
        HashSet<String> Q = new HashSet<>();
        
        //그래프 노드를 Q에 저장
        //출발지가 아닌 경우 distance, 이전 노드 초기화
        for(String key: graph.keySet()){
            Q.add(key);
            if(!key.equals(source)){
                distances.put(key, INFINITY);
                preNode.put(key, "");
            }
        }
        
        //Q가 빌때 까지 반복
        while(!Q.isEmpty()){
            //현재 Q안에서 최소 distance인 node 찾은 후 꺼내기
            String minNode = "";
            double minNodeDistance = INFINITY;
            for(String node: Q){
                if(distances.get(node) < minNodeDistance){
                    minNode = node;
                    minNodeDistance = distances.get(node);
                }
            }
            Q.remove(minNode);
            
            //거리 최소 node의 이웃 노드까지 거리 Map 읽어 오기
            //최소 node 까지 거리 + 이웃 노드까지 거리 < 현재 이웃 노드의 최소 거리 이면 distance, preNode 갱신
            HashMap<String, Double> minNodeMap = graph.get(minNode);
            for(String key: minNodeMap.keySet()){
                double distance = minNodeDistance + minNodeMap.get(key);
                if(distance < distances.get(key)){
                    distances.put(key, distance);
                    preNode.put(key, minNode);
                }
            }
        }
        
        Result result = new Result();
        result.distances.putAll(distances);
        result.preNode.putAll(preNode);
        
        return result;
    }
}

참조

https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98