23.06.22

2023. 06. 22 목요일

 

- 다익스트라 알고리즘? 전제조건? 특징?

: 최단 경로를 구하는 알고리즘. 그리디 + DP의 형태. (최소 간선 채택 + 최단 경로 업데이트용 메모리(배열) 필요)

각 노드별 최단 거리를 적을 배열과 방문 배열을 만들어놓고, 최댓값으로 초기화한다.

Math.min(자신이 현재 가지고 있는 값 + 간선 비용, 기존 해당 노드의 값)으로 연결된 노드를 최신화하고, 이후 방문하지 않은 노드 중 가장 값이 적은 노드를 채택하여 진행한다.

이때 주체가 된 노드는 방문 노드에서 true로 바꿔준다.

 

전제조건은 간선에 음의 가중치가 없어야 한다.

 

한 노드에서 다른 모든 노드로의 최단 경로가 구해진다.