エッジの重みが正の有向グラフ G (場合によってはサイクルを含む) が与えられ、ソース s からD[v]すべての頂点までの最小距離vも与えられます (D はこのように配列です)。問題は、線形時間で s から v までのN[v] = number長さのパスの配列を見つけることです。D[v]
さて、これは私がかなり長い間苦労してきた宿題の問題です。私は次の考えに沿って作業していました: G の非巡回サブグラフを適切に選択してサイクルを削除し、サブグラフで s から v への最短経路を見つけようとしています。
しかし、私は何をすべきかを明示的に把握することはできませんので、何をすべきかについての質的なアイデアのように、助けていただければ幸いです.