[그래프] 다익스트라

✔ 다익스트라

다익스트라란?

• 엣지가 모두 양수인 그래프에서 출발 노드와 모든 노드 간의 최단 거리를 구하는 알고리즘
• V는 노드 수, E는 엣지 수일때, 시간 복잡도는 O(ElogV)

다익스트라 과정

1. 인접 리스트로 그래프를 표현
2. 최단 거리 배열을 만들고, 출발 노드는 0, 이외의 노드는 무한으로 초기화
3. 최단 거리 배열에서 현재 값이 가장 작은 노드를 고름
4. 선택된 노드에 연결된 엣지의 값을 바탕으로 다른 노드의 값을 업데이트
   • Min(선택 노드의 최단 거리 배열의 값 + 엣지 가중치, 연결 노드의 최단 거리 배열의 값)
   • 이때 한 번 선택된 노드가 다시 선택되지 않도록 방문 배열을 만들어 처리
5. 모든 노드가 선택될 때까지 과정을 반복

 

Do it! 알고리즘 코딩테스트 with JAVA

https://inf.run/w9Tn