이것 저것 뚝딱거리는 사람 이것 저것 뚝딱거리는 사람

플로이드-워셜(Floyd-Warshall) 알고리즘 그래프의 모든 노드 간 최단 거리를 구하는 알고리즘이다. 시간 복잡도는 $O(n^3)$이므로 모든 최단 경로가 필요하지만 노드의 수가 적을 때 사용할 수 있다. 아이디어 한 노드(k)가 다른 두 노드(a, b)의 중간지점이라 생각한다면, a에서 b로 가는 경로는 $a-k-b$ 이다. (k가 a혹은 b라면 경로는 a-b가 된다.) $a-k-b$를 모두 조사한다면 a-b간 최단 경로를 알 수 있다. 아래와 같은 그래프를 가정하면 2를 중간 노드로 둘 경우, 2-2-3, 2-2-5, 3-2-5의 세 가지 경로의 값을 알 수 있다. 이 값들 중에서 3-2-5의 경우 3-5로 가는 경로보다 값이 작으므로 업데이트 해준다. 코드 for k in range(1, n..

그래프 트리와 같이 노드와 간선으로 연결된 형태를 그래프라고 한다. 싸이클이 형성될 수 있기 때문에 계층적 자료구조라기 보다는 전체를 나타내는 형태로 생각할 수 있다. 따라서 부모-자식 관계나 루트노드 같은 성질이 없다. 위 그림에서 A-B-E-C-A의 사이클이 있다. 그래프에는 여러가지 특징이 있다. 먼저, 방향이 있는 그래프와 방향이 없는 그래프로 나눌 수 있다. 위에서 그린 그래프는 방향이 없는 그래프이고, 방향이 있는 그래프는 다음과 같다. 방향이 있을 때는 해당 방향으로만 진행할 수 있다는 특징이 있다. 다음으로는 모든 노드가 연결되어있지 않아도 된다는 것이다. 이를 비연결그래프, disjoint 그래프라 한다. 반면 모든 노드가 서로 연결되어있는 그래프는 완전그래프라 한다. 간선에 가중치를 둘..