指定された頂点を通過する有向グラフの最短経路を見つける

Question

有向グラフがあります。指定された頂点を通過する有向グラフで最短経路を得る方法です。

Answer 1

実際にこの問題はNPのクラスに該当します。よく知られているNP問題であるハミルトニアンパスがこの問題に還元されるためです。だからあなたはブルートフォースサーチや近似アルゴリズムを使うかもしれません。