깊은 밤을 날아서

개요 그래프에서 최단거리를 구하는 알고리즘입니다. 특징은 아래와 같습니다. 모든 노드 간의 최단 거리 구하기 가능 음수 가중치 에지가 있어도 수행 가능 동적 계획법의 원리를 이용해 알고리즘을 구성 시간복잡도는 O(V^3) 구현 방법 시작 노드에서 도착 노드까지의 최단 경로를 구할 때 그 중간에 있는 노드 K가 존재한다면 시작 노드→K, K → 도착노드와 같은 부분 경로도 최단 경로라는 원리입니다. sp_list[S][E] = min(sp_list[S][E], sp_list[S][K] + sp_list[K][E]) 인접 행렬로 구현하는 방법입니다. 리스트 선언 및 초기화 sp_list[S][E]는 노드 S에서 E까지의 최단 거리를 저장하는 리스트 S와 E가 같은 칸은 0, 다른 칸은 무한으로 초기화 최단 ..

1. 다익스트라 알고리즘 개요 그래프에서 최단 거리를 구하는 알고리즘 입니다. 특정 출발 노드에서 다른 노드로 가는 최단 거리를 모두 구하기 때문에 출발 노드가 고정되어 있을 때 사용 가능합니다. 추가적으로 에지들의 가중치 또한 항상 양수여야 합니다. 기능 특징 시간 복잡도(노드 수: V, 에지 수: E) 출발 노드와 모든 노드 간의 최단 거리 탐색 에지는 모두 양수 O(ElogV) 구현 방법 간단하게 말하자면 BFS로 탐색을 진행하되, 다음 탐색 지점을 방문하지 않은 노드 들 중 가장 가까운 곳부터 선택하도록 하는 방법입니다. 위와 같이 항상 갈 수 있는 가장 최솟값인 경로만 택함으로써 결과적으로 각 노드는 출발 노드로부터 최단 경로만에 도달하게 됩니다.(간선의 가중치가 모두 양수가 아니라면 돌아올수록..