다익스트라와 플로이드-워셜, 그리고 크루스칼 알고리즘

1. 다익스트라 알고리즘

특정 지점(Node)에서 다른 모든 Node 까지의 최단거리를 구하는 알고리즘.
시작지점이 정해지면 해당 지점으로 부터 다른 모든 지점 까지 가는 최단 경로를 구하는 알고리즘이라고 생각하면 된다.

2. 플로이드-워셜 알고리즘

모든 지점(Node) 쌍들간의 최단거리를 구하는 알고리즘.
다익스트라 알고리즘이 특정 시작 지점과 다른 모든 지점 까지의 최단 거리를 구했다고 생
플로이드-워셜 알고리즘은 3중첩 for문을 사용하면 되기 때문에 구현이 간단하다. 그러나 곰곰히 생각해보면 가장 외곽에 있는 for 문이 중간 Node를 지정하는데 선택하는 중간 노드의 순서에 상관없이 최단 거리가 나온다는게 직관적으로 이해가 가지 않았다. 얼핏 생각하기에는 특정 노드를 경유하는 최단값이 먼저 반영되는지 또는 나중에 반영되는지에 따라서 최종 결과값이 달라질 것 같았다.
그러나 간단한 예시를 통해서 그렇지 않음을 확인 할 수 있다.

3. 크루스칼 알고리즘

크루스칼 알고리즘은 최소 신장 트리 (Minimum Spanning Tree)를 구하는 알고리즘이다. 최소 신장 트리는 그래프 입장에서 봤을 때, 모든 노드를 지나는 최단 거리라고 생각하면 된다. 또한 이때 서로소 집합이라는 자료구조가 사용된다.