安い経路のほうが、高い経路より多くの区間を使うことがあります。幅優先探索の距離だけでは、異なる辺のコストを比べられません。経路の暫定コストを保持し、まだ確定していない最小のコストを繰り返し確定させます。緩和では新しい経路で隣接ノードが改善するかを確かめ、最初に見つけた値はあくまで暫定です。課題で許されていれば、コスト0の辺も有効です。
資源も消費する経路もあります。免除を残したまま着いた駅は、免除を使った後に着いた同じ駅とは異なります。乗り継ぎに上限があるときは、1回の更新で誤って複数の新しい区間を使わないよう、コストの層を分ける必要があります。最安の経路を数えるときは、距離と数の両方を保持し、改善したら数を置き換え、同じなら足します。コードを書く前に、距離が何を意味するかを述べてください。練習問題のネットワークは規模に上限があるので、密な走査でもヒープを使う実装でも実用的です。