728x90 반응형 prim algorithm2 [Algorithm] 최단 경로 탐색(Shortest Path) - 다익스트라 알고리즘(Dijkstra Algorithm) 개요 ◎ 다익스트라 알고리즘이란? ◎ 그림 예시 ◎ 구현 코드 - 인접 행렬 (Java) ◎ 시간 복잡도 - 인접 행렬 ◎ 구현 코드 - 힙 (Java) ◎ 시간 복잡도 - 힙 안녕하세요. J4J입니다. 이번 포스팅은 다익스트라 알고리즘에 대해 적어보는 시간을 가져보려고 합니다. 다익스트라 알고리즘이란? 다익스트라 알고리즘은 그래프에서 정점 간의 최단 경로를 탐색하기 위해 사용되는 알고리즘 기법으로 시작 정점에서부터 다른 정점들까지 도달하기 위해 필요한 최소 거리를 찾기 위해 사용됩니다. 다익스트라를 이용해 최단 경로를 구하는 식은 D[i][j] = min(D[i][j], D[i][k] + D[k][j])이고 이를 이용해 최단 경로를 구하는 방법은 다음과 같습니다. 예를 들어 A, B, C, D, E 정.. 2021. 1. 31. [Algorithm] 최소 신장 트리(MST, Minimum Spanning Tree) 개요 ◎ 최소 신장 트리란? ◎ 신장 트리란? ◎ 그림 예시 ◎ 신장 트리 특징 ◎ 최소 신장 트리 구현 알고리즘 안녕하세요. J4J입니다. 이번 포스팅은 최소 신장 트리에 대해 적어보는 시간을 가져보려고 합니다. 최소 신장 트리란? 최소 신장 트리는 신장 트리들 중 가중치의 합이 가장 작은 신장 트리를 의미합니다. 여기서 가중치라고 하는 것은 그래프에서 길(간선)을 지나기 위해 지불되는 값이라고 생각하면 됩니다. 예를 들어 A에서 출발하여 C에 도착한다고 가정해 보겠습니다. A→B 가중치: 5 B→C 가중치: 8 이면 A→C로 이동하기 위한 가중치의 합은 13이 되는 것입니다. 신장 트리란? 신장 트리란 최소한의 길(간선)을 이용하여 모든 정점들을 이동 가능하도록 만들어진 트리입니다. 따라서 하나의 그.. 2021. 1. 24. 이전 1 다음 728x90 반응형
