그래프 알고리즘 정리 - 파이썬

그래프 알고리즘 분류 그래프는 최소신장트리와 최단거리 문제로 나눌 수 있다. 각기 사용되는 알고리즘이 다르다. MST (최소신장트리) 크루스칼 - 간선기준 가장 작은것부터 연결, 음의 간선 가능 프림 - 정점기준 정점에 연결된 가장 작은 간선으로 연결, 음의 간선 가능 간선 개수가 적으면 크루스칼, 정점 개수가 적으면 프림 적용 최단경로 다익스트라 (우선순위큐 heapq 사용, 단일 정점 최단경로) 벨만-포드 (음의 가중치, 경로 추적 가능) 플로이드 와샬 (음의 가중치, 3중포문, 모든 정점 사이 최단거리) shortest path faster algorithm 크루스칼 간선을 정렬하여 가중치가 작은 간선부터 연결 사이클이 발생하면 연결하지 않음 O(E * log(E)) 프림 한 정점의 간선 중 가중치..