여러 지점을 최소 비용으로 모두 연결하려 합니다. 최소 신장 트리는 최단 경로와 무엇이 다른가요?

최소 신장 트리는 연결된 무방향 가중 그래프의 모든 정점을 연결하되 간선 비용 합을 최소화하는 트리입니다. 한 출발점에서 각 정점까지의 거리를 최소화하는 최단 경로 트리와 목적 함수가 다릅니다. 통신선의 총 설치 비용을 줄이는 문제에는 MST가 맞지만, 특정 출발지의 배송 거리나 장애 우회 경로가 목표라면 최단 경로 또는 중복 연결 설계를 따로 해야 합니다.

운영 제약은 별도로 추가합니다

정점 V개를 하나의 트리로 연결하려면 간선이 V-1개이고 사이클이 없어야 합니다. 사이클의 간선 하나를 제거해도 연결이 유지되므로, 양수 비용의 전체 연결 문제에서 불필요한 중복 간선을 제거한 트리가 후보가 됩니다. 하지만 MST에서 두 지점 사이의 트리 경로가 원래 그래프의 최단 경로라는 뜻은 아닙니다. 총 설치 길이가 짧은 대신 특정 두 지점 사이에 우회가 길어질 수 있습니다. 이를 최소 신장 트리(Minimum Spanning Tree)와 최단 경로 트리(shortest-path tree)의 목적 차이라고 부릅니다.

그래프가 연결되지 않았으면 모든 정점을 하나의 트리로 잇는 해가 없습니다. 각 연결 성분별 최소 신장 숲을 반환할지 실패로 처리할지 계약을 정합니다. 음수 간선도 신장 트리의 정의와 간선 수 제약 안에서는 허용됩니다. 최단 경로처럼 음수 사이클을 무한히 추가하는 문제가 아니라, 가능한 신장 트리들의 총비용을 비교하는 문제이기 때문입니다. 다만 간선 의미가 설치·철거 비용인지와 중복 경로 요구가 있는지는 별도로 확인하겠습니다.

운영 제약은 별도 문제로 둡니다

MST는 장애 시 유일한 경로만 남을 수 있어 네트워크에서 가용성 요구를 충족하지 못합니다. 두 개 이상의 경로, 최대 지연, 용량, 장애 허용을 요구하면 최소 비용 연결만으로는 부족하고 survivable network 설계나 제약이 있는 spanning 구조를 검토해야 합니다. 동일 비용 간선이 많으면 여러 MST가 존재할 수 있으므로 총비용과 연결성을 정답 기준으로 두겠습니다.

검증은 연결·비연결 그래프, 중복·동일 가중치, 음수 가중치, 고립 정점을 포함합니다. 결과에 V-1개 간선이 있는지, 모든 정점이 연결되는지, 사이클이 없는지, 작은 그래프의 가능한 모든 트리 중 비용이 최소인지 확인합니다. 문제를 ‘모두 연결’이라고만 읽지 말고 전체 합을 줄이는지, 출발점별 이동을 줄이는지, 장애 우회를 요구하는지 먼저 결정하겠습니다.

최소 신장 트리는 연결된 무방향 가중 그래프의 모든 정점을 연결하는 신장 트리 중 간선 비용 합이 최소인 트리입니다. 출발점에서 각 정점까지의 거리를 최소화하는 최단 경로 트리와 목적이 다릅니다. V개 정점의 신장 트리는 V-1개 간선이고 사이클이 없지만, MST의 두 지점 사이 경로가 원래 그래프의 최단 경로라는 보장은 없습니다.

사이클을 제거하면 연결을 유지한다는 설명은 선택된 신장 트리가 이미 연결된 상태에서 여분 간선을 제거할 때의 논리입니다. 음수 간선이 있어도 신장 트리는 간선 수가 고정된 연결 부분 그래프이므로, 음수 사이클을 무한히 추가하는 최단 경로와 같은 문제는 없습니다. 그래프가 비연결이면 하나의 신장 트리가 없고 최소 신장 숲인지 실패인지 정합니다. 장애 우회·용량·지연 요구는 MST와 별도로 검증하겠습니다.

예를 들어 A-B=2, B-C=2, A-C=3이면 MST는 A-B와 B-C로 총비용 4입니다. 그러나 이 트리에서 A에서 C까지는 4가 들고 원래 그래프의 직접 간선 3보다 멉니다. A를 출발점으로 한 최단 경로 트리는 A-B와 A-C로 총 간선 비용 5가 될 수 있습니다. 두 결과가 다른 이유는 알고리즘의 성능이 아니라 최소화하는 목적이 다르기 때문입니다.