다익스트라1 [알고리즘 개념] 다익스트라 다익스트라 알고리즘 한 그래프의 특정 시작점에서 다른 모든 정점으로 가는 최단거리를 각각 구해주는 알고리즘을 말한다. 다른 정점까지의 최단 경로를 구하는 과정에서 모든 정점을 탐색하기에 최단 경로를 보장할 수 있다. 단, 가중치가 양수일 때 가능하다.(음수일 땐 벨만포드를 사용하면 된다) 참고로 그래프 알고리즘의 종류 대표적으로 다익스트라, 벨만포드, 플로이드 워셜이 있다. 다익스트라 알고리즘을 어떻게 구현하면 될지 알아보자. 예시로 5개의 정점이 있고 1번 정점에서 출발해 2~5번 정점까지의 최단거리를 구해야 할 때 먼저 입력받은 값을 각각 u(시작 위치), v(도착 위치), w(가중치)라고 한다면 u.append(v,w)가 된다. 만약 V(정점)의 개수가 적다면 위의 인접 리스트 방식이 아닌 인접 행.. 2023. 12. 5. 이전 1 다음
