깊은 밤을 날아서

K번째 최단 거리 찾기 개요 다익스트라 알고리즘을 이용하여 K번째 최단 거리를 구합니다. 구현 방법 최단 경로 리스트를 2차원 리스트로 설정하여 내부를 K개의 최단 경로로 채웁니다. K번째 경로를 찾기 위해서 여러 번 노드가 쓰일 수도 있으므로 방문 리스트는 따로 적용하지 않습니다. 위의 내용을 기억하며 아래의 최단 거리 리스트 채우기 규칙을 따릅니다. 최단 경로 리스트 및 그래프 인접 리스트를 초기화합니다. 우선 순위 큐에서 연결된 노드와 가중치 데이터를 가져옵니다. 연결 노드의 K번째(마지막) 경로와 신규 경로를 비교해 신규 경로가 더 작을 때 K번째 경로에 값을 업데이트합니다. 이때 경로가 업데이트되는 경우 거리 배열을 오름차순으로 정렬하고 우선순위 큐에 연결 노드를 추가합니다. 큐가 비워질때까지 ..

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