다익스트라 알고리즘

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

public class Main {
    static class Graph {
        Map<String, List<Node>> nodes = new HashMap<>();
        
        public void addNode(String vertex, List<Node> adjacentNodes) {
            nodes.put(vertex, adjacentNodes);
        }
        
        public List<Node> getAdjacentVertex(String vertex) {
            return nodes.get(vertex);
        }
    }
    
    static class Node implements Comparable<Node>{
        String vertex;
        int distance;
        
        public Node (String vertex, int distance) {
            this.vertex = vertex;
            this.distance = distance;
        }
        
        public int getDistance() {
            return distance;
        }
        
        public String getVertex() {
            return vertex;
        }

        @Override
        public int compareTo(Node o) {
            return distance < o.distance ? -1 : 1;
        }
    }
    
    public static int dijkstra(String start, String end) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        List<Node> nodes = graph.getAdjacentVertex(start);
		pq.add(new Node(start));        

        for(Node n : nodes) {
            pq.add(n);
        }
        
        minDistance.put(start, 0);
        
        while(!pq.isEmpty()) {
            Node curNode = pq.poll();
            List<Node> adjacentList = graph.getAdjacentVertex(curNode.getVertex());
            
            if(minDistance.get(curNode.getVertex()) < curNode.getDistance()) {
                continue;
            }
            
            for(Node n : adjacentList) {
                if(minDistance.get(curNode.getDistance())+n.getDistance() < minDistance.get(n.getVertex())) {
                    pq.add(new Node(n.getVertex(), minDistance.get(curNode.getDistance())+n.getDistance()));
                    minDistance.put(n.getVertex(), minDistance.get(curNode.getDistance())+n.getDistance());
                }
            }
        }
        
        return minDistance.get(end);
    }
    
    public static Map<String, Integer> minDistance = new HashMap<>();
    public static Graph graph = new Graph();
    
    public static void main(String[] args) {
        minDistance.put("S", Integer.MAX_VALUE);
        minDistance.put("A", Integer.MAX_VALUE);
        minDistance.put("B", Integer.MAX_VALUE);
        minDistance.put("C", Integer.MAX_VALUE);
        
        List<Node> sAdj = new ArrayList<>();
        sAdj.add(new Node("A", 2));
        sAdj.add(new Node("C", 12));
        
        List<Node> aAdj = new ArrayList<>();
        aAdj.add(new Node("B", 3));
		aAdj.add(new Node("S", 2));
        
        List<Node> bAdj = new ArrayList<>();
        bAdj.add(new Node("C", 4));
		bAdj.add(new Node("A", 3));
        
        List<Node> cAdj = new ArrayList<>();
        cAdj.add(new Node("S", 12));
		cAdj.add(new Node("B", 4));
        
        graph.addNode("S", sAdj);
        graph.addNode("A", aAdj);
        graph.addNode("B", bAdj);
        graph.addNode("C", cAdj);
        
        int ret = dijkstra("S", "C");
        System.out.println(ret);
        
    }
    
}​