가중 그래프
가중 그래프는 그래프 이론 용어로, 꼭짓점과 꼭짓점 사이를 잇는 변(간선)에 가중치(비용)가 주어진 그래프를 말한다.[1]
가중 그래프 중 유향 그래프를 네트워크(Network)라고도 한다. 각 정점들을 도시, 연결선들을 도로라고 가정하면, 가중치는 각 도로를 지나기 위한 비용이나 도시 사이의 거리라고 생각할 수 있다. 가중치는 양수와 음수 모두를 가질 수 있으며, 최단 경로 문제는 가중치의 합이 최소가 되는 경로를 구하는 문제로, 각각의 경우에 따라 문제를 해결하는 알고리즘이 서로 다르다.