1

私は実際にこの割り当てられた問題についてしばらく考えていましたが、どこにも行けません...ベルマンフォード、ダイクストラ、フロイドウォーシャルを知っています。

ほとんどの場合、これはV頂点とEエッジの標準的な最短経路問題であり、各エッジの長さはL、色はCです。これらは双方向です。

唯一の制約は、同じ色の2つの連続するエッジに移動せずに、最短経路の長さを見つける必要があるということです。

Vが小さければフロイド・ウォーシャルは機能しますが、Vは（3、50000）によって制限されます。

何か助けはありますか？考え？

4

2 に答える 2

1

ダイクストラのようなものを試してみてください。ただし、各頂点への特定の色で終わる最短経路を追跡してください。

于 2012-10-10T03:41:17.687 に答える
0

http://paginas.matem.unam.mx/publicaciones/phocadownloadpap/Preliminares-DF/879.pdfの論文、弧色の有向グラフの最短H制限パスは、かなり標準的なパスファインディングアルゴリズムを使用しているようですが、各頂点の色ごとに個別の情報を保持します。有向グラフ用ですが、無向グラフから有向グラフを作成できると思います。

于 2012-10-10T04:22:11.167 に答える