ベルマンフォード法での負閉路の見つけ方

ベルマンフォード法において、負閉路が存在すれば出力する方法を教えてもらいたいです。
まだ学びたてで良く分からないのですが、擬似コード（で良いのでしょうか？）も添えてくれると幸いです。

質問者からの補足コメント

• 負閉路の存在確認でなくて、負閉路を出力したいのですが…

  No.1の回答に寄せられた補足コメントです。 補足日時：2018/01/03 22:56

No.1 回答者： stomachman 回答日時： 2018/01/03 22:51

ベルマン・フォード法の原理がお分かりならあまりにも簡単な話。

グラフに重みの総計が負になるループ（負閉路）がないという前提のもとでは「処理をこれだけの回数繰り返せば必ず最短距離が得られる」という回数が予め分かっている。ということはつまり、その所定の回数だけ繰り返した後、続けていくら繰り返しをしても最短距離が更新されることはない。逆に、もし負閉路が存在するならば、その所定の回数だけ繰り返した後にもう一度繰り返しをやれば、必ず最短距離が更新される。

No.2 ベストアンサー 回答者： stomachman 回答日時： 2018/01/04 10:02

No.1へのコメントについてです。

「負閉路が存在すれば出力する」のではなくて、「負閉路が存在すればどの部分グラフが負閉路なのかを出力する」というご質問ですか。
　グラフのどの閉路についても、もしそれが負閉路でないならば、どのnode(vertex)への最短経路もその閉路を一周しているということはない、ということは自明です。つまり、どれかのnodeへの最短経路に閉路があれば、それは負閉路だということです。逆に負閉路があればどれかのnodeへの最短経路にその負閉路が含まれる、という風にするには、以下のように追加の繰り返しを行えば良い。
　余計な繰り返しをしてみれば、最短距離が変化しない部分グラフPが決まり、Pは負閉路の上流側にあるんで、負閉路を探すにあたっては無視して宜しい。そこでさらに、P以外の部分Qについて余計な繰り返しを充分に（すなわち、負閉路の可能な最大長よりも多く）やってみれば、Qのどのnodeへの「最短経路」もPには繋がっていない状態になる。この時、「最短経路」とは名ばかりで、これを辿っても出発点に戻れなくなっています。
　そこで、Qのどれかのnodeを選んで、これに至る最短経路を遡って行けば、いずれ負閉路を回ることになり、すなわち経路上に同じnodeが二度以上現れる。あとはお分かりでしょう。

この回答へのお礼

解説ありがとうございます。
なるほど、頂点への最短経路で確認するのですか。
おかげ様で理解が進みました。

お礼日時：2018/01/04 10:44