목록CS/알고리즘 (11)
LALA's blog
[ 알고리즘 / 그래프 / 최단 경로 탐색 ] 다익스트라(Dijkstra) 알고리즘
그래프의 정점끼리의 최단 경로를 구하는 문제 1) 하나의 정점에서 다른 하나의 정점까지의 최단 경로를 구하는 문제 (1:1) 2) 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제 (1:N) 3) 하나의 목적지로 가는 모든 최단 경로를 구하는 문제 (N:1) 4) 모든 최단 경로를 구하는 문제 (N:N) 다익스트라 알고리즘은 간선에 가중치가 있는 그래프에서 1:N 최단거리를 구하는 알고리즘이다. 사이클이 없는 방향성 그 래프에 한해서만 사용할 수 있다. 1. 다익스트라 알고리즘? Dist[] 배열에 시작점으로부터 자신에게 이르는 경로의 길이를 ∞(무한대)로 초기화 시작 정점의 경로 길이를 0으로 초기화하고(시작 정점 -> 시작 정점 거리는 0) + 방문한 정점으로 체크 방문한 정점들과 연결되..
CS/알고리즘
2020. 4. 7. 14:46