지나지 않을 점 최단경로

다음 그림에서 $\mathrm{C}$에서 $\mathrm{D}$까지 최단거리의 경로의 수는

ⅰ) $\mathrm{A} \rightarrow C \rightarrow X \rightarrow D \rightarrow B$: $1$ ⅱ) $\mathrm{A} \rightarrow C \rightarrow Y \rightarrow D \rightarrow B$: $\displaystyle 1 \times \frac{4 !}{3 !} \times \frac{4 !}{3 !} \times 1 = 16$ ⅲ) $\mathrm{A} \rightarrow C \rightarrow Z \rightarrow D \rightarrow B$: $\displaystyle 1 \times \left( \frac{4 !}{2 ! 2 !} - 1 \right) \left( \frac{4 !}{2 ! 2 !} - 1 \right) \times 1 = 25$ 이므로 $1 + 16 + 25 = 42$(가지) 마찬가지로 $\mathrm{E}$에서 $\mathrm{F}$까지 최단거리의 경로의 수도 $42$(가지)이다. 따라서 구하는 최단거리의 경로의 수는 $42 + 42 = 84$(가지)