728x90 반응형 heap2 [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 - 프림 알고리즘(Prim Algorithm) 개요 ◎ 프림 알고리즘이란? ◎ 그림 예시 ◎ 구현 코드 - 인접 행렬 (Java) ◎ 시간 복잡도 - 인접 행렬 ◎ 구현 코드 - 힙 (Java) ◎ 시간 복잡도 - 힙 ◎ 특징 안녕하세요. J4J입니다. 이번 포스팅은 프림 알고리즘에 대해 적어보는 시간을 가져보려고 합니다. 프림 알고리즘이란? 프림 알고리즘은 대표적인 MST 구현 알고리즘 중 하나로 정점을 기준으로 갈 수 있는 가중치가 가장 작은 길(간선)을 선택한 뒤 다음 정점을 방문하며 MST를 만드는 기법입니다. 예를 들어 A, B, C, D, E 정점이 있다고 가정해보겠습니다. A ↔ C 가중치: 3 A ↔ D 가중치: 5 B ↔ C 가중치: 4 B ↔ D 가중치: 4 C ↔ E 가중치: 2 D ↔ E 가중치: 1 이고 A 정점에서 출발한다면.. 2021. 1. 27. 이전 1 다음 728x90 반응형
