n駅の場合、駅から(i,j <= n)までの直行時間を表すn*n行列Aが与えられます。A[i][j]ij
駅間を移動する人は常に最短時間を求めます。2 つの駅番号a,が与えられた場合b、それらの間の最小移動時間の計算はどのように進めればよいでしょうか?
この問題は、グラフ理論を使わずに、つまり行列 A だけで解決できますか?
1873 次
2 に答える
5
それを解決するには、グラフ理論が必要です。より具体的には、ダイクストラのアルゴリズムが必要です。グラフを行列として表現することは、そのアルゴリズムにとって利点でも欠点でもありません。
ただし、ダイクストラのアルゴリズムでは、すべての距離が非負である必要があることに注意してください。何らかの理由で行列に負の「距離」がある場合は、代わりに低速のBellman-Ford アルゴリズムを使用する必要があります。
(行列演算の使用に本当に熱心で、非常に遅くなることを気にしない場合は、非常に単純な行列演算に基づくFloyd-Warshall アルゴリズムを使用して、すべてのペア間の最短経路を計算できます。ステーション (大量のオーバーキル) を選択してから、興味のあるペアを選択してください...)
于 2012-08-06T21:15:20.217 に答える
-4
これは、NP 困難な巡回セールスマン問題と非常によく似ています。
于 2012-08-06T21:11:25.533 に答える