연결망의 두 목적
여러 지점을 최소 비용으로 연결해 기반 시설을 만드는 일과 한 지점에서 다른 지점까지 빨리 이동하는 일은 다른 요구다. 같은 지점과 간선을 사용해도 최적화할 값이 달라지면 답도 달라진다. 그래프를 만들기 전에 간선 비용이 무엇이며 어떤 결과를 최소화할지 정해야 한다.
세 지점의 예시
A와 B의 간선 비용이 2, B와 C가 2, A와 C가 3인 무방향 그래프를 생각하자. 전체를 연결하는 최소 신장 트리는 비용 2인 두 간선을 골라 합계 4를 만든다. 하지만 그 트리에서 A에서 C로 가면 비용은 4다. 원래 그래프에서는 비용 3인 직접 간선이 더 짧다. 전체 연결의 최적성이 모든 두 점의 최단 이동을 보장하지 않는 사례다.
최단 경로 트리의 차이
하나의 출발점에서 각 정점까지 최단 경로를 모은 트리도 생각할 수 있다. 이는 그 출발점에 대한 거리 요구를 만족시키지만 간선 비용의 전체 합을 최소화하는 트리와 같을 필요는 없다. 출발점을 바꾸면 구조가 달라질 수 있다. 트리라는 결과 모양이 같아 보여도 최적화 목적은 구분해야 한다.
연결되지 않은 입력
모든 정점이 서로 이어져 있지 않으면 전체를 연결하는 신장 트리는 존재하지 않는다. 이때 각 연결 성분의 트리를 모은 신장 숲을 구할 수 있다. 최단 경로에서도 도달할 수 없는 목적지는 별도로 처리해야 한다. 결과가 없거나 여러 부분으로 나뉘는 상황을 정상적인 입력의 일부로 정의한다.
적용 전의 확인
간선이 방향을 가지는지, 음수 비용이 있는지, 한 출발점만 필요한지에 따라 사용할 최단 경로 알고리즘의 조건이 달라진다. 최소 신장 트리의 일반적인 정의를 방향 그래프에 그대로 적용하지도 않는다. 자료의 형식과 알고리즘의 지원 조건을 맞춘 뒤 작은 사례에서 목적 함수가 실제로 만족되는지 확인한다.