ダイクストラの最短経路法が機能していると仮定すると、これを使用して、有向グラフが強く接続されているかどうかを判断するにはどうすればよいですか?
1 に答える
2
最短経路アルゴリズムが、すべてのノードが入力ノードから到達可能であると言うのはなぜですか?
あなたが話している最短経路アルゴリズムは何ですか？
強連結有向グラフに最短経路のようなものはありますか?
グラフが接続されている限り、最短経路が含まれます。bfs、ダイクストラ、ベルマンフォードなどのさまざまなアルゴリズムがすべて存在し、一意のプロパティを持つグラフ内の最短パスを見つけます
グラフを逆にしても、すべてのノードに到達できるのはなぜですか?
これは、グラフが強く接続されている場合にのみ当てはまります。また、これは、グラフが強く接続されているかどうかを判断する多くの方法の 1 つにすぎません。もう 1 つの方法は、各ノードから dfs を実行することです。すべてのノードが最後のノードまで毎回タッチされる限り、グラフは強く接続されます。
これは、グラフが強く接続されていることをどのように証明しますか?
証明は暗記していませんが、証明は存在し、Google から見つけることができます。
最短経路アルゴリズムを使用してグラフが強く接続されているかどうかを判断するコードを見つけることができる場所はありますか?
グラフが強く接続されているかどうかを判断するには、まずグラフに対して dfs を実行します。すべてのノードに到達可能な場合は、エッジの方向を逆にして dfs を再度実行します。すべてのノードがまだ到達可能な場合、グラフは強く接続されています
自分で最短経路アルゴリズムを使用してこれをどのようにコーディングする必要がありますか?
Google で dfs を調べる
于 2016-05-20T02:22:05.913 に答える