728x90
반응형
양의 그래프에서 최소 비용 찾는 문제를 만났을 때 무슨 알고리즘을 쓸 지 판단이 어려운데요.
고민할 필요 없이 정확히 판단할 수 있도록 정리해 보았습니다.
판단 척도
항목 | 판단 척도 | 사용 알고리즘 |
가중치 | +(방향), +(양방향), -(방향) 가능 -(양방향) 불가능 → -사이클 발생 |
플로이드 워셜, 벨만포드 |
+(방향), +(양방향) 가능 -(방향), -(양방향) 불가능 |
다익스트라 | |
입력 최대 범위 |
V정점 200개 이하 (너무 작은 범위인 경우 무조건 플로이드 의심) |
플로이드 워셜 |
(V+E)*log(V) 계산해서 2천만 이하 | 다익스트라 | |
(V+E) 계산해서 2천만 이하 | 벨만포드 | |
필요한 정보 |
한 노드에서 다른 모든 노드로의 최단 경로 비용 | 다익스트라, 플로이드 워셜, 벨만 포드 |
모든 노드에서 다른 모든 노드로의 최단 경로 비용 | 플로이드 워셜 |
※ 참고
파이썬 1초 20,000,000번 연산
데이터 20,000,000 => O(N)
데이터 1,000,000 => O(NlogN)
데이터 4~5,000 => O(N^2)
데이터 100~200 => O(N^3)
반응형
'Python > 알고리즘' 카테고리의 다른 글
파이썬(python) 알고리즘 - 최단 경로 (플로이드 워셜) (0) | 2021.09.05 |
---|---|
파이썬(python) 가장 긴 증가하는 부분수열 (LIS) (2) | 2021.08.27 |
파이썬(python) 투 포인터 (0) | 2021.05.13 |
파이썬(python) 알고리즘 - 최단 경로 (다익스트라) (0) | 2021.05.09 |
파이썬(python) 알고리즘 - 동적 계획법 푸는 방법 (0) | 2021.04.28 |