20/01/22 15:24:21 F8rWZ32I.net
359 ：１３２人目の素数さん [] ：2020/01/22(水) 10:18:34.48 ID:hYYepbWN (1/7)
Cormen, Leiserson, Rivest, Stein著『Introduction to Algorithms 3rd Edition』を読んでいます。
最短経路を求めるBellman - Fordのアルゴリズムってその正しさの証明が面白いですね。
360 ：１３２人目の素数さん [] ：2020/01/22(水) 10:47:05.97 ID:hYYepbWN (2/7)
Donald Knuth著『The Art of Computer Programming vol.1 3rd Edition』を読んでいます。
1箇所、記号の説明の足りないところを見つけましたので、メールで本人にレポートしました。
もしかしたら小切手がもらえるかもしれませんね。
362 ：１３２人目の素数さん [] ：2020/01/22(水) 14:39:01.40 ID:hYYepbWN (3/7)
Cormen著『Algorithms Unlocked』を読んでいます。
DACの最短路を求めるアルゴリズムの正しさの証明ですが、非常に面白いですね。
363+3 ：１３２人目の素数さん [] ：2020/01/22(水) 14:39:27.04 ID:hYYepbWN (4/7)
訂正します：
Cormen著『Algorithms Unlocked』を読んでいます。
DAGの最短路を求めるアルゴリズムの正しさの証明ですが、非常に面白いですね。
364 ：１３２人目の素数さん [] ：2020/01/22(水) 14:44:10.12 ID:hYYepbWN (5/7)
>>363
エレガントすぎます。
365 ：１３２人目の素数さん [] ：2020/01/22(水) 14:48:34.80 ID:hYYepbWN (6/7)
>>363
数学でもここまで痛快な証明はあまりないのではないでしょうか？
366+1 ：１３２人目の素数さん [] ：2020/01/22(水) 14:53:28.49 ID:hYYepbWN (7/7)
>>363
本には、single-source shortest path problemとして書いてありますけど、
トポロジカルソートの一番端の点をソースにしてアルゴリズムを適用すれば全点間の最短路を簡単に求められますよね。