최단경로
-
최단 경로 (다익스트라, 플로이드 워셜 알고리즘)알고리즘/이론 2021. 3. 14. 20:53
본 글은 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 책을 공부하며 기록합니다. 단, iOS를 공부하고 있기 때문에 swift 언어로 코드를 바꿔보고 있습니다. 최단 경로 가장 짧은 경로를 찾는 알고리즘. '길 찾기' 문제 라고도 불린다. 상황에 맞는 효율적 알고리즘이 정해져 있다! 예 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 보통 그래프를 이용하여 표현되고, 각 지점은 노드로, 지점 간 연결된 도로는 간선으로 표현된다. 보통은 최단 거리를 출력하는 문제가 많다. 대표적 알고리즘 다익스트라 최단 경로 알고리즘 플로이드 워셜 벨만 포드 알고리즘 다익스트라 최단 경로 알고리즘과 플로이드 워셜 알고리즘이 가..