플로이드 와샬 알고리즘 - 최단 거리 알고리즘 (2) 최단 거리 알고리즘 중에 하나인 플로이드 와샬 알고리즘을 알아보겠다. 그래프를 보면 1번에서 5번으로 가기 위한 방법은 아주 많은데 플로이드 와샬 알고리즘은 어떻게 가장 짧은 거리를 알 수 있을까? 그래프 초기화 1 2 3 4 5 6 1 0 5 9 14 many many 2 5 0 36 many 47 many 3 9 36 0 22 55 88 4 14 many 22 0 many 31 5 many 47 55 many 0 11 6 many many 88 31 11 0 먼저 그래프를 초기화한다. 그림은 무방향인데 방향이 있어도 똑같다. 방향이 있다면 없는 방향은 그냥 many라고 생각하고 큰 수를 넣어주든가 하자. 다만 +의 영향으로 Int.Max value..

노드 정점들을 연결하는데 가장 적은 비용으로 연결하려면 어떻게 해야할까?? 위의 질문에 해결하기 위한 대표적인 방법으로 크루스칼 알고리즘을 들 수 있습니다. 크루스칼 알고리즘으로 모든 노드를 지나면서 사이클이 생기지 않고 가장 적은 비용을 가는 경로를 알 수 있습니다. 아래에 4개의 그림이 있습니다. 4개의 그림 모두 그래프의 모든 정점을 지납니다. 또한 순환고리 즉 사이클이 생기지 않은 연결들입니다. 이러한 연결들을 신장 트리라고 합니다. 각 각의 그림의 가중치 합은 다음과 같습니다. 왼쪽 위 : 3+4+1 = 8 오른쪽 위 : 4+3+2 = 9 왼쪽 아래 : 4+5+2 = 11 오른쪽 아래 : 3+2+1 = 6 가장 적은 가중치의 합을 가진 그림은 오른쪽 아래에 있는 그래프입니다. 가장 작은 값을 갖..