LimeCoding

다익스트라 알고리즘이란?(What is a Dijkstra Algorithm?) 다익스트라 알고리즘은 가중치를 가지는 그래프에서 한 정점을 기준으로 다른 정점들에 도달하는 최단 경로를 찾는 알고리즘이다. 이때 중요한 것은 가중치가 음수를 가지면 안된다는 것이다. 가중치가 음수를 가지면 다익스트라 알고리즘이 동작할 수 없다. 다익스트라 알고리즘은 인접한 정점으로 가는 간선중 가장 적은 비용을 가지는 간선을 택한다. 알고리즘 수행중 새로운 경로가 생기면 그 경로를 기록하고 이후에 생기는 또 다른 경로와 비교하면서 최단 경로를 탐색한다. 다익스트라 알고리즘을 수행하기 위해서는 먼저 그래프를 인접 행렬로 표현해야 한다. 위 그림에서 인접 행렬을 보면 무한대 표시가 보인다. 이는 정점이 인접하지 않는다는 표시이다..

솔린 알고리즘이란?(What is a Sollin Algorithm) 솔린 알고리즘은 최소 비용 신장 트리를 구하는 알고리즘중 하나로 크루스칼 알고리즘과 프림 알고리즘처럼 간선을 하나씩 선택하는 것이 아닌 동시에 여러 개의 간선을 선택하여 트리를 만드는 알고리즘이다. 솔린 알고리즘을 설명하기 전 포레스트(Forest)라는 용어의 정의가 필요하다. 포레스트란 서로 연결되지 않은 트리들의 집합 또는 연결되지 않은 비순환 그래프의 집합을 말한다. 그림으로 표시하면 다음과 같다. 그림을 보면 두 그래프는 서로 순환하지 않은 그래프이면서 서로 연결되어 있지 않다. 이런 자료 구조를 포레스트라고 한다.(정점만 있는 그래프나 하나의 트리도 포레스트가 될 수 있다.) 이제 솔린 알고리즘을 설명할 수 있다. 솔린 알고리..

프림 알고리즘이란?(What is a Prime Algorithm) 프림 알고리즘은 최소 비용 신장 트리를 구하는 알고리즘중 하나이다. 가중치를 가지는 그래프에서 가장 작은 가중치를 가지는 엣지를 시작으로 인접한 정점과 연결된 엣지들중 가장 작은 가중치를 가지는 엣지들을 선택해 나가면서 신장 트리를 만드는 것이 프림 알고리즘이다. 프림 알고리즘이 엣지를 하나씩 선택한다는 점에서는 크루스칼 알고리즘과 같지만 인접한 정점의 엣지들만 선택한다는 점에서는 크루스칼 알고리즘과 다른 점을 보여준다. 다음은 프림 알고리즘 수행 과정이다. 그래프 및 가중치 표 다음은 프림 알고리즘에 사용될 그래프와 그래프의 가중치를 표로 나타낸 것이다. 그럼 프림 알고리즘을 수행해보자. (4, 6) 선택 먼저 시작은 가장 작은 가중치..