- データ構造,アルゴリズム,デザインパターン総合ｽﾚ 2
852 ：デフォルトの名無しさん[]：2016/04/05(火) 16:33:18.67 ID:m6kqb6v+ - ダイクストラのアルゴリズムの正しさの証明がよく分からないのですが、
何かいい本はありますか？
| - データ構造,アルゴリズム,デザインパターン総合ｽﾚ 2
853 ：デフォルトの名無しさん[]：2016/04/05(火) 16:46:05.13 ID:m6kqb6v+ - http://imgur.com/MdPoKq5.jpg
http://imgur.com/PRjr5CT.jpg
http://imgur.com/41t2x4S.jpg
↑ダイクストラのアルゴリズムの正しさの証明についてですが、
3枚目の赤で囲ったあたりが分かりません。
この証明、分かる人いますか？
| - データ構造,アルゴリズム,デザインパターン総合ｽﾚ 2
854 ：デフォルトの名無しさん[]：2016/04/05(火) 16:50:41.63 ID:m6kqb6v+ - 3枚目の画像で、
「d(x) = d(y) + l(y, x) となっているはずである。」
と書かれていますが、その後、このことは証明中で使われていないように見えます。
これは何なんでしょうか？
| - データ構造,アルゴリズム,デザインパターン総合ｽﾚ 2
855 ：デフォルトの名無しさん[]：2016/04/05(火) 16:58:30.51 ID:m6kqb6v+ - 3枚目の画像に、
「d(x) = d(y) + l(y, x) となっているはずである。」
と書かれていますが、
d(x) ≦ d(y) + l(y, x)
ということしか言えないかと思います。
これについてはどうですか？
|
|
