重みなしの有向グラフのある点からある点までの最短経路を求める方法として

質問

重みなしの有向グラフのある点からある点までの最短経路を求める方法として、優先度付きキューにまだ追加していないノードを追加していく方法がありますが、2番目に短い経路を求めるにはどうすればいいのでしょうか。

キューへの追加は一度だけという条件を取っ払って、何度も追加してもいいように変更すると、求めることができますが、計算に時間がかかってしまいます。

回答No.1

Tacosan · ベストアンサー

ちょっと調べてみた.
よくわからんけど, 始点から他の点までの「最短距離」と「2番目に短い距離」の両方を記録してる.

参考URL：

http://answers.yahoo.com/question/index?qid=20090619061142AAKjxKq

お礼

ありがとうございました