연결에 수치를 더한다
장소 A와 B 사이에 연결이 있다는 정보에 더해 이동 비용이 7이라는 값을 붙일 수 있다. 같은 연결 구조라도 가중치가 다르면 가장 싼 경로나 연결망이 달라질 수 있다.
그림의 길이와 다르다
간선을 길게 그렸다고 가중치가 크다는 뜻은 아니다. 별도의 숫자나 규칙으로 지정한 값이 가중치다. 그림에서 가까운 정점을 찾는 것과 가중치 합이 작은 경로를 찾는 것은 구별한다.
값의 조건을 정한다
모든 가중치가 양수인지, 0이나 음수를 허용하는지에 따라 문제의 성질과 사용할 알고리즘이 달라진다. 서로 다른 단위의 비용을 의미 없이 더하지 않도록 수치의 해석도 먼저 정한다.
서로 다른 최적화
두 정점 사이의 최단 경로는 경로의 가중치 합을 최소화한다. 최소 신장 트리는 모든 정점을 연결하는 트리의 전체 가중치 합을 최소화한다. 같은 가중 그래프라도 목표가 다르면 답도 달라진다.
관련 문서
유향 그래프 / 무향 그래프 / 간선 (그래프 이론) / 정점 (그래프 이론) / 최단 경로 / 최소 신장 트리 / 신장 트리