宿題ではないのです。

ある本に、頂点 s から t への最短経路を計算する方法として、
s から ｔ へのあらゆる経路の長さを考えて、最小の経路を選ぶとすると、
経路の数が O(n!) だから現実的ではない

という話が書いてあります。

ところが、計算してみると、 O(n!) は荒い評価であって、 O((n-1)!) とできますね。