Algorithm/그래프&최단경로
-
[Java]플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)Algorithm/그래프&최단경로 2021. 4. 15. 22:44
*플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) -> 플로이드-워셜 알고리즘은 음수 사이클이 없는 그래프내의 각 모든 정점에서 각 모든 정점에 까지의 최단거리를 모두 구할 수 있는 알고리즘이다. 다익스트라 알고리즘과는 다르게 그래프에 음수 사이클만 존재하지 않으면, 음의 가중치를 갖는 간선이 존재해도 상관이 없다는 것이다. ※음수 사이클 : 사이클의 모든 경로를 지나 원래 지점으로 돌아 왔을때, 최종적인 비용이 음수가 되는 경우. *플로이드-워셜 알고리즘의 이해 -> 플로이드-워셜 알고리즘은 다이나믹 프로그래밍 기법을 사용한 알고리즘이고, 인접 행렬을 이용하여 각 노드간 최소 비용을 계산한다. -> 플로이드-워셜 알고리즘은 모든 노드에서, 모든 노드로 가는 최소 비용을 단계적으로 ..
-
[Java]크루스칼 알고리즘(Kruskal Algorithm)Algorithm/그래프&최단경로 2021. 4. 15. 17:15
*크루스칼 알고리즘(Kruskal Algorithm) -> 크루스칼 알고리즘은 그래프에서 최소 비용 신장 부분 트리(최소 신장 트리 : Minimum Spanning Tree(MST))를 찾는 알고리즘이다. ※ 최소 신장 트리, 신장 트리와 같은 용어를 조금 더 자세히 알고 싶다면 위키백과를 참고하도록 하자. ko.wikipedia.org/wiki/%EC%8B%A0%EC%9E%A5_%EB%B6%80%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84 신장 부분 그래프 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 그래프의 신장 부분 나무 그래프 왼쪽의 그래프는 오른쪽과 같이 총 8개의 신장 부분 나무 그래프들을 갖는다. 그래프 이론에서, 신장 부분 그래프(身長部分gr..
-
[Java]그래프의 표현Algorithm/그래프&최단경로 2021. 3. 12. 00:41
*그래프의 표현 ->프로그래밍을 하다보면 그래프를 만들어야 하는 경우가 발생할 수 있는데, 프로그래밍에서 그래프를 표현하는 방법은 크게 2가지(인접 행렬, 인접 리스트)로 나뉜다. ->인접 행렬 : 수학에서 행렬은 그래프를 표현하는데 사용되기도 하였다. 따라서 프로그래밍에서 2차원 배열은 행렬의 성질을 갖는다는 점을 활용하여 마찬가지로 그래프를 표현할 수 있다. 기본적으로 인접행렬을 이용한 그래프 표현은 각 인덱스를 정점이라고 생각하고, 정점이 교차하는 지점(좌표)을 연결된 상태라고 표시해주면 된다. (1) 무향 그래프 : 방향을 가지지 않는 그래프를 말한다. 따라서, 행렬이 대칭적으로 같은 값을 갖는 특징을 갖는다. (2) 유향 그래프 : 방향을 가지고 있는 그래프를 말한다. 따라서, 무조건 행렬이 대..
-
[Java]다익스트라 알고리즘(Dijkstra Algorithm)Algorithm/그래프&최단경로 2021. 3. 12. 00:40
*다익스트라 알고리즘(Dijkstra Algorithm) -> 다익스트라 알고리즘은 음의 가중치(음의 간선, 음의 값)가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단거리를 구하는 알고리즘을 말한다. -> 초기 모델은 O(V^2)의 시간복잡도를 가졌다. 이후 우선순위 큐 등을 이용한 고안된 알고리즘이 탄생했고, 현재는 O((V+E)log V)의 시간복잡도를 가지고 있다(만일 연결 그래프라면 O(ElogV)까지 시간 복잡도를 줄일 수 있다고 한다). 일반적으로는 그래프가 희소 그래프인 경우에 우선순위 큐를 이용하는 것이 낫다고 한다. ※음의 가중치를 가지면 안되는 이유는 최소 비용의 음의 무한대 발산, 그리디 알고리즘 적용 불가능 등이 있다. 후자는 제일 아래에 있는 다익스트라 알고리즘 정당성 증명을..