최단경로알고리즘1

• [파이썬] '최단경로' 개념 및 예제 그리디와 다이나믹 프로그래밍이 그대로 적용! 실제 코딩 테스트에서는 최단 경로를 모두 출력하는 문제보다, 단순히 최단 거리를 출력하는 문제 많이 출제됨! 최단거리 알고리즘 종류) 1. 다익스트라 최단거리 2. 플로이드 워셜 => 1,2가 많이 출제됨 3. 벨만 포드 1. 다익스트라 - 그래프의 노드 중 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로 구함 - '음의 간선 없어야함' - 그리디 알고리즘에 속함 ( 매번 '가장 비용 적은 노드' 선택하므로) 원리) 1. 출발 노드 설정 2. 최단 거리 테이블 초기화 (무한대로) 3. 방문 안 한 노드 중 최단거리 가장 짧은 노드 선택 ( 우선순위 큐를 사용하여 간단히 가능) 4. 해당 노드를 거쳐 다른 노드로 가는 비용 계산하여 최단 거리 테이블 .. Algorithm/이론 2021. 2. 9.