public class DijkstraMain {

	private static final int GRAPH_SIZE = 6;
	private static final boolean[] visited = new boolean[GRAPH_SIZE + 1];
	private static final int[] d = new int[GRAPH_SIZE + 1]; // 최단 거리 테이블

	static class Node {
		private int index;
		private int distance;

		public Node(int index, int distance) {
			this.index = index;
			this.distance = distance;
		}

		public int getIndex() {
			return index;
		}

		public int getDistance() {
			return distance;
		}
	}

	private static List<List<Node>> graph;

	public static void main(String[] args) {
		initGraph();
		initDTable();
		dijkstra();

		System.out.println("Arrays.toString(d) = " + Arrays.toString(d));
	}

	private static void initDTable() {
		Arrays.fill(d, Integer.MAX_VALUE);
	}

	private static void dijkstra() {
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(1);
		d[1] = 0;
		do {
			Integer poll = queue.poll();
			visited[poll] = true;
			List<Node> nodes = graph.get(poll);
			for (Node node : nodes) {
				int nodeIndex = node.getIndex();
				// 방문할 노드 넣기
				if (!visited[nodeIndex]) {
					queue.offer(nodeIndex);
				}
				// 최단 경로 갱신
				if (d[poll] + node.getDistance() < d[nodeIndex]) {
					d[nodeIndex] = d[poll] + node.getDistance();
				}
			}
		} while (!queue.isEmpty());
	}

	private static void initGraph() {
		graph = new ArrayList<>();
		for (int i = 0; i <= GRAPH_SIZE; i++) {
			graph.add(new ArrayList<>());
		}
		graph.get(1).add(new Node(2, 2));
		graph.get(1).add(new Node(3, 5));
		graph.get(1).add(new Node(4, 1));

		graph.get(2).add(new Node(3, 3));
		graph.get(2).add(new Node(4, 2));

		graph.get(3).add(new Node(2, 3));
		graph.get(3).add(new Node(6, 5));

		graph.get(4).add(new Node(3, 3));
		graph.get(4).add(new Node(5, 1));

		graph.get(5).add(new Node(3, 1));
		graph.get(5).add(new Node(6, 2));
	}
}