![[알고리즘] 데이크스트라(Dijkstra)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FJEJJD%2FbtsBGkIePKO%2FuHCbZPDvqqbRO3kLKsAGE0%2Fimg.png)
CS/알고리즘2023. 12. 9. 18:27[알고리즘] 데이크스트라(Dijkstra)
Concept그리디 알고리즘의 한 분류다이나믹 프로그래밍 메모이제이션 기법 활용부분 문제 : 한 정점까지의 최단거리는 방문하는 여러개의 정점들의 최단거리로 이루어져있음.주어지는 그래프에서 시작 정점으로부터 각 정점까지의 최단경로를 찾는 알고리즘Feature우선순위 큐와 거리배열(DP)을 활용하여 로직 구성.한 정점 V까지의 최단거리를 구할 때 V까지로 가는 여러 정점들의 최단 거리 정보를 활용한다는 특징을 가짐.가중치를 가진 그래프에서 최단거리를 구할 때 쓰이는 알고리즘음수 가중치를 가진 그래프에서는 사용불가.우선순위 큐를 활용함으로써 시간복잡도 : O(N * NlogN)Implement인접 리스트를 통한 구현우선 데이크스트라 소스코드를 보자.private static int dijkstra(int st..