Data Structures, Algorithms, & Applications in C++
Chapter 17, Exercise 27

The simple paths and their lengths are
  1. 1,2,5,3; length is 10

  2. 1,2,5,8,6,3; length is 9

  3. 1,4,3; length is 28

  4. 1,4,6,3; length is 27

  5. 1,4,7,8,6,3; length is 28


The shortest path is 1,2,5,8,6,3.