알고리즘

다익스트라 알고리즘은 시작 노드로부터 모든 다른 노드로의 최단 경로를 구한다.다익스트라 알고리즘 동작 원리 1\. 출발 노드 설정 2\. 최단 거리 테이블 초기화 3\. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택 4\. 해당 노드를 거쳐 다른 노드로 가

다익스트라 알고리즘 수행 시 매 번 최단 거리가 가장 짧은 노드에 방문하여 해당 노드를 거쳐 가는 거리를 계산하여 최단 거리 테이블을 갱신한다.이전 포스트에서는 get_smallest_node() 함수를 통해매번 최단 거리 테이블을 선형 탐색하여 최소값을 구하는 방식으

다익스트라 알고리즘이 특정 한 노드에서 모든 노드로의 최단 경로를 계산했다면,플로이드 워셜 알고리즘은 모든 노드에서 모든 노드로의 최단 경로를 계산한다.다익스트라 알고리즘에서는 매 단계 마다 시작 노드로부터 최단 경로가 가장 짧은 특정 노드를 선택하고 그 외 모든 노드

1. Disjoint Set (서로소 집합) 수학에서 서로소란 아래와 같이 공통 원소가 없는 두 집합을 의미한다. > A: {1, 3, 5}        &nbsp B:{2, 4, 6} 알고리즘에서 서

이전 포스트에서는 Union-Find 기법을 통한 서로소 집합 알고리즘을 알아봤다. 서로소 집합 알고리즘을 응용하면 그래프의 싸이클 판별과 크루스칼 알고리즘 등을 구현할 수 있다. 이번에는 그래프의 싸이클 판별에 대해 알아보고자 한다. 1. 그래프의 Cycle

이전 포스트에서 다뤘던 Union-Find 기법을 통한 서로소 집합 알고리즘과 이를 통한 싸이클 판별을 이용해서 크루스칼 알고리즘을 구현해보고자 한다. > Kruskal Algorithm은 싸이클 없이 최소 비용의 간선을 택하여 모든 노드를 연결하는 그래프이론이다.