목록다익스트라 (1)

from palette import colorful_colors

[알고리즘 with 파이썬] - 최단거리(다익스트라, 플로이드 워셜)

참고서적: 이것이 코딩테스트다 with 파이썬 graph를 이용해 최단거리를 이용하는 방법이다. 다익스트라는 특정 노드에서 다른 노드로 가는 최단거리를 구하는 방법이고, 시간복잡도는 짜는 방법에 따라 O(V^2), O(ElongV)다. (V는 간선의 개수, E는 간선의 개수) 간선은 모두 양수여야 한다. 플로이드 워셜은 모든 노드에서 모든 노드로 가는 최단거리를 구하는 방법이고, DP를 이용해 구한다. 시간복잡도는 O(V^3)이다. 음수 가중치 간선이 있어도 수행할 수 있다. 다익스트라 알고리즘 먼저 거리를 무한으로 초기화하고, 출발노드부터 시작해 방문하지 않은 노드를 선택해 인접한 다른 노드로 가는 비용을 체크한다. 이때 해당 노드를 거쳐 다른 노드로 가는 거리가 다른 노드의 기존 거리보다 작다면 갱신..
알고리즘/알고리즘 with 파이썬 2023. 9. 22. 10:54
이전 Prev 1 Next 다음