Dijkstra

출발 노드와 모든 노드 간의 "최단 거리" 탐색

- weight가 있을 때

- 에지는 모두 양수일 때 

---

0

Adjacency matrix로 구현해도 좋지만, 시간 복잡도 및 N의 크기에 대비해 Adjacency graph로 구현한다

 

 

1

최단 거리 배열 D[N]을 만들고

- 출발 노드 0

- 나머지 노드는 Integer.MAX_VALUE로 할당

 

2

cycle unit

- D[N]에서 가장 값이 작은 노드를 고른다(출발 노드에서 시작)

- 해당 노드와 연결된 노드에 에지의 가중치를 업데이트

- Min(D[selected] + edge weight, D[connected])

 

3

kaiten space

- 모든 노드가 선택될 때까지 반복

- boolean[] visited를 만들어 중복 처리

- 출력