基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

経路の組合せ数は18あるので、すべての経路について総運賃を考えます。

1. [出発地→1→4→7→目的地]　6＋8＋10＋4＝28
2. [出発地→1→4→8→目的地]　6＋8＋11＋7＝32
3. [出発地→1→5→7→目的地]　6＋8＋7＋4＝25
4. [出発地→1→5→8→目的地]　6＋8＋5＋7＝26
5. [出発地→1→6→7→目的地]　6＋7＋8＋4＝25
6. [出発地→1→6→8→目的地]　6＋7＋3＋7＝23
7. [出発地→2→4→7→目的地]　5＋4＋10＋4＝23
8. [出発地→2→4→8→目的地]　5＋4＋11＋7＝27
9. [出発地→2→5→7→目的地]　5＋6＋7＋4＝22
10. [出発地→2→5→8→目的地]　5＋6＋5＋7＝23
11. [出発地→2→6→7→目的地]　5＋5＋8＋4＝22
12. [出発地→2→6→8→目的地]　5＋5＋3＋7＝20
13. [出発地→3→4→7→目的地]　2＋6＋10＋4＝22
14. [出発地→3→4→8→目的地]　2＋6＋11＋7＝26
15. [出発地→3→5→7→目的地]　2＋8＋7＋4＝21
16. [出発地→3→5→8→目的地]　2＋8＋5＋7＝22
17. [出発地→3→6→7→目的地]　2＋10＋8＋4＝24
18. [出発地→3→6→8→目的地]　2＋10＋3＋7＝22

したがって最も安くなる経路は「出発地→2→6→8→目的地」、総運賃は20になります。