重み付き最短経路
辺の重みが非負の有向グラフから経路と到達距離を確認します。
例の値が入力されています。直接確認するか、値を変更してみてください。
入力はブラウザで処理されます。再読み込みすると例の値に戻ります。
使い方と例
d(v)=min(d(v),d(u)+w(u,v))
既定グラフはA→C→B→Dで総重み4になります。
ノード30個・辺100本以内で、負の重みは非対応です。
よくある質問
最短経路の辺は自動で双方向になりますか?
いいえ。有向辺です。双方向には逆向きの辺も入力します。
最短経路の終点に到達できない場合は?
経路なしと無限距離を表示します。未接続を距離0として扱いません。
計算基準と参考資料
- Princeton Algorithms: Shortest Paths
d(v)=min(d(v),d(u)+w(u,v))