반납함 두 곳은 어디에 놓아야 할까?

그림에서 무엇을 볼까요?

행사장 입구·무대·잔디밭·강변 네 구역과 구역 사이 보행 거리를 연결한 경로 그림

강변 행사장에는 입구 A, 무대 B, 잔디밭 C, 강변 D의 네 구역이 있다. 인접 구역의 보행 거리는 A-B 2, A-C 5, B-C 2, B-D 4, C-D 2로 두자. 반납함을 A와 B에 두면 입구와 무대는 편하지만 강변 D에서는 가까운 C를 거쳐 B까지 4를 걸어야 한다. A와 D에 두면 네 구역에서 가장 먼 거리는 2로 줄어든다.

여기서 첫 목표는 가장 불편한 구역의 거리를 줄이는 것이다. 누구도 2보다 멀리 걷지 않게 하는 배치는 공정성 관점에서 매력적이다. 네트워크의 최단 거리는 연결선 하나의 길이가 아니라 목적지까지 이어지는 경로 길이의 합으로 계산한다.