이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 최단 경로 문제 각 간선의 가중치 합이 최소가 되는 두 정점 사이의 경로를 찾는 문제 그래프의 종류와 특성에 따라 각각 최적화된 다양한 최단 경로 알고리즘이 존재 가장 유명한 것이 다익스트라 알고리즘 다익스트라 알고리즘 항상 노드 주변의 최단 경로만 택하는 대표적인 그리디 알고리즘 단순하고 실행 속도가 빠름 노드 주변을 탐색할 때 BFS를 이용 다익스트라 알고리즘 특징 임의의 정점을 출발 집합에 더할 때, 그 정점까지의 최단 거리 계산이 끝났다고 가정 - 즉, 탐색을 위한 출발노드가 갖는 최단거리는 최단거리임이 보장되어야함 따라서, 음수를 처리할 수 없음 - 벨만-포드 알고리즘과 같이 음수 사용이 가능한 알고리즘 사용..
