위키득계정 ↗
기술

최단 경로와 최소 신장 트리

최단 경로와 최소 신장 트리기술
최단 경로
목표 사이의 이동 비용 최소화
최소 신장 트리
전체 연결 비용 최소화
일반적인 대상
가중 그래프
판정 기준
경로 길이와 선택한 간선 합계
최단 경로는 특정 출발점에서 목적지까지의 비용을 줄이는 문제이고 최소 신장 트리는 모든 정점을 연결하는 간선들의 전체 비용을 줄이는 문제다. 목적 함수가 다르므로 한 답을 다른 문제의 답으로 사용하면 안 된다.

연결망의 두 목적

여러 지점을 최소 비용으로 연결해 기반 시설을 만드는 일과 한 지점에서 다른 지점까지 빨리 이동하는 일은 다른 요구다. 같은 지점과 간선을 사용해도 최적화할 값이 달라지면 답도 달라진다. 그래프를 만들기 전에 간선 비용이 무엇이며 어떤 결과를 최소화할지 정해야 한다.

세 지점의 예시

A와 B의 간선 비용이 2, B와 C가 2, A와 C가 3인 무방향 그래프를 생각하자. 전체를 연결하는 최소 신장 트리는 비용 2인 두 간선을 골라 합계 4를 만든다. 하지만 그 트리에서 A에서 C로 가면 비용은 4다. 원래 그래프에서는 비용 3인 직접 간선이 더 짧다. 전체 연결의 최적성이 모든 두 점의 최단 이동을 보장하지 않는 사례다.

최단 경로 트리의 차이

하나의 출발점에서 각 정점까지 최단 경로를 모은 트리도 생각할 수 있다. 이는 그 출발점에 대한 거리 요구를 만족시키지만 간선 비용의 전체 합을 최소화하는 트리와 같을 필요는 없다. 출발점을 바꾸면 구조가 달라질 수 있다. 트리라는 결과 모양이 같아 보여도 최적화 목적은 구분해야 한다.

연결되지 않은 입력

모든 정점이 서로 이어져 있지 않으면 전체를 연결하는 신장 트리는 존재하지 않는다. 이때 각 연결 성분의 트리를 모은 신장 숲을 구할 수 있다. 최단 경로에서도 도달할 수 없는 목적지는 별도로 처리해야 한다. 결과가 없거나 여러 부분으로 나뉘는 상황을 정상적인 입력의 일부로 정의한다.

적용 전의 확인

간선이 방향을 가지는지, 음수 비용이 있는지, 한 출발점만 필요한지에 따라 사용할 최단 경로 알고리즘의 조건이 달라진다. 최소 신장 트리의 일반적인 정의를 방향 그래프에 그대로 적용하지도 않는다. 자료의 형식과 알고리즘의 지원 조건을 맞춘 뒤 작은 사례에서 목적 함수가 실제로 만족되는지 확인한다.

관련 문서

알고리즘 / 너비 우선 탐색 / 깊이 우선 탐색