파이썬(python) 알고리즘 - 최단 경로 (다익스트라, 벨만포드, 플로이드 워셜)

양의 그래프에서 최소 비용 찾는 문제를 만났을 때 무슨 알고리즘을 쓸 지 판단이 어려운데요.

고민할 필요 없이 정확히 판단할 수 있도록 정리해 보았습니다.

 

판단 척도

---

항목	판단 척도	사용 알고리즘
가중치	+(방향), +(양방향), -(방향) 가능 -(양방향) 불가능 → -사이클 발생	플로이드 워셜, 벨만포드
	+(방향), +(양방향) 가능 -(방향), -(양방향) 불가능	다익스트라
입력 최대 범위	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) 알고리즘 - 최단 경로 (플로이드 워셜)