私は無向グラフを扱っています。私は、グラフ内のすべての可能な非環式のパスを見つける必要がある：私はPythonのscipyのダウンロードやMathWorks社のMATLABのいずれかを使用しています最適解：グラフ問題の可能なすべての非循環パス
with G(V,E)
find all subsets of V that are acyclic paths
- 方が適切であろう。 これに巧妙な解決法はありますか？
私は
（Wikiを参照）幅優先探索とそれを達成しようとしている私も、MATLABでこのツールボックスを持っている：http://www.mathworks.com/matlabcentral/fileexchange/4266-grtheory-graph-theory-toolboxが、私の問題のための簡単な解決策はありませんようです。
PS。トランジットネットワーク設計問題：事実上のように記載されている問題は、私は問題だと思い、事前に ラファウ
をpassangersと演算子のコスト（つまり、都市部に最適な地下鉄網）
感謝を最小限に抑え、そのようなトランスポートネットワークを探しますあなたのPSに記載されているようにNPの問題があるかもしれません。そうであれば、非常に限られた数のノード（N〜< = 20）を持つグラフに対してのみ簡単な解法が存在する。他の解は近似的であり、局所最適値のみを生じる。質問に記載されているように問題を解決するには、ノード順序のすべての順列を計算するだけです。この場合も、ノード数が比較的少ない（おそらく20を超えるが多分ではない）場合、これは計算上実行不可能となる。
私のグラフは疎なグラフなので、結果はすべての並べ替えに近いとは思いません。私のグラフ構造は木のようです。 –
OK - 申し訳ありませんが、私はもっと役に立たない。 –
すべての頂点のペアの間に最短パスしか必要ないか、実際にはすべてパスですか？
計算結果は、最適化問題の領域になります。最適解が見つかるようにするには、できるだけ最短のパスだけでなく、すべての可能なパスを取得する必要があります。 –
これに関連する議論があります：http://mathoverflow.net/questions/18603/finding-all-paths-on-undirected-graph私は一般的にあなたは徹底的な検索を余儀なくされると思います。 –
答えを受け入れるには_nice_でしょうか – ThomasMcLeod