私の教授は、単一のソース ノードからネットワーク内の他のすべてのノードへの実装を望んでいます。彼は、親ノードを使用して最短経路を追跡すると言いましたが、これがアルゴリズムのコンテキストで何を意味するのかわかりません。
コードを実行するネットワークに対して出力距離がすべて正しいという意味で、コードを多かれ少なかれ適切に実装できます。
しかし、ほとんどのオンライン リソースでは、ノードを訪問し、隣接するすべてのノードを探索したら、それらを訪問済みとしてマークすることについて説明しています。たとえば、ノード A と B がノード C に隣接しており、A までの新しい距離が B の距離よりも小さい場合、ノード C を訪問済みとしてマークしますか? そして、ノード A にたどり着き、それが私を導く経路が、実際にはすでに記録されている距離を実際に大きくする原因になることに気付いたらどうなるでしょうか?
Dystra のアルゴリズムからパス (単なるコストではなく) を取得するには、各ノードのベスト コストを保存するのではなく、ペア (best_cost、from_where) を保存します。from-where は、best_cost を生成した隣接ノードへのハンドルです。
次に、from_where ポインターを原点までたどって、最適なパスを取得できます。「親」は、2タプル/ペアの from_where 要素の彼の名前だと思います。
私の教授は、単一のソース ノードからネットワーク内の他のすべてのノードへの実装を望んでいます。彼は親ノードを使用して最短経路を追跡すると言いましたが、これがアルゴリズムのコンテキストで何を意味するのかわかりません。
つまり、ノードごとに、どのノードから来たノードであるかを最短パスで保存するということです。このようにして、最短経路の距離だけでなく、最短経路自体も見つけるためにアルゴリズムを完了したら、最短経路を逆の順序で歩くことができます。
しかし、ほとんどのオンライン リソースでは、ノードを訪問し、隣接するすべてのノードを探索したら、それらを訪問済みとしてマークすることについて説明しています。
距離が最も短い未訪問のノードであった後に、訪問済みのノードをマークします。負の距離がない限り、より短い距離のパスを見つけることはできません (それでも、グラフにゼロ未満の距離のサイクルがある場合にのみ問題になります)。