ITeus

Dijkstra 알고리즘은 특정 Node를 시작점으로 하여, 해당 시작점부터 각 Node의 최단거리를 구하는 알고리즘입니다. 알고리즘은 1. 최초 시작점을 제외, 나머지 Node까지의 거리를 ∞로 설정한다. 2. 시작점에서 각 Node까지의 거리를 갱신 3. 시작점에서 가장 가까운 Node로 이동 4. 2~3을 반복하며, 더이상 이동할 Node가 없을때까지 반복 예시를 보면서 좀더 알아보겠습니다. Kruskal 알고리즘을 포스팅 할때 사용한 숙련된 조교를 한번더 이용하겠습니다. B Node를 시작점으로 진행하겠습니다. B와 연결된 모든 Node와의 거리를 해당 Node의 Distance라고 설정하면 [5,0,11,7,8,2]

그래프에서 모든 Node를 포함하면서, Cycle을 형성하지 않는 Tree를 신장트리라고 합니다. 아래 그림을 보면, 하나의 Graph에 대해서 여러가지의 신장트리가 나온는 것을 확인할 수 있습니다. 이때, Node를 이어주는 간선의 가중치(색갈마다 값이 다르다고 생각합시다)가 모두 다르다면, 간선의 총 합을 최소로하는 최소신장트리 가 존재하게 됩니다. Kruskal 알고리즘은 욕심쟁이 방법론을 활용해서 최소신장트리를 구하는 알고리즘 입니다. 알고리즘은 1. 간선의 가중치들을 작은 순서부터 나열한다 2. 나열된 가중치를 하나씩 연결한다 3. Node의 연결상태가 Cycle을 형성하는지 확인하고, Cycle을 형성하면 해당 간선을 Drop한다. 4. 1~3반복 아래는 예시 Graph와 거리행렬 입니다. 이..

Floyd알고리즘은 두 노드간의 최단거리를 산출하는 알고리즘을 활용해서, 모든 Node간의 최단 거리를 산출하는 알고리즘 입니다. 다음 예시를 봅시다.A~E까지의 5개의 Node이있고, 서로간에 위와같은 거리가 존재할 때, 해당 상태는 우측과같은 거리행렬로 나타낼 수 있습니다(무한대는 갈수 없다는것을 뜻함) A,C,E의 관계를 봅시다.A->C로 바로 연결되어 있기 때문에 A->C로 가는 거리는 4로 생각할 수 있으나, 최소의 거리는 아닙니다.A->E->C로 이동할 경우 2+1 = 3 이 논리가 Floyd알고리즘의 핵심입니다. 위 논리를 활용해서, 거리행렬을 모두 갱신해주면 알고리즘이 종료됩니다. 시작점(N개)와 끝점(N-1)를 비교하고, 이때 중간점(N-2)의 반복비교가 발생하기 때문에 O(N3)의 시간..