ありがとうございます。ワーシャルフロイド法については動画の中では軽く紹介しただけでしたので、突っ込んだコメントをいただけて嬉しく思います。ご指摘の通りワーシャルフロイド法はループを回す順番が決まっていて、i,j,kの三つ組をデタラメな順番で調べるのではなく「i→jはkを経由するほうが短くなるか」のkに関するループが一番外側に来るような順番で調べる必要があります。（だから(i,j,k)ではなく(k,i,j)という順で書くことが多いですね。） ただ、ループを回す順番が間違っていたとしても、それを3回繰り返せば正しい答えが得られます。 Ikumi Hide, Soh Kumabe, Takanori Maehara: Incorrect implementations of the Floyd-Warshall algorithm give correct solutions after three repeats arxiv.org/pdf/1904.01210.pdf
Well it was worth it learning japanese. I was just reading up on Dijkstra and Bellman-Ford a couple minutes ago, and this lesson was a great way to supplement it
![COLOMBIA vs. CHILE [4-0] | RESUMEN | ELIMINATORIAS SUDAMERICANAS | FECHA 10](http://i.ytimg.com/vi/TDjN4W3yy1k/mqdefault.jpg)
28:50 「全ての三つ組を調べ尽くして行列Lの更新が全部完了したとき」と言っていますが、これは「同じ三つ組を複数回使うかもしれないが、どの三つ組を使っても L を更新出来なくなったとき」と解釈すれば正しいですが、「全ての三つ組を一度ずつ調べて緩和操作をした後」と解釈すると正しくない(例: 前半のグラフで(東京, 新横浜, 小田原) を最初に調べてしまう)のに注意が必要そうですね。
また、「どの三つ組を使っても〜」の解釈の場合、インスタンスと三つ組を調べる順序によっては、頂点数の指数時間かかることがありますね(例: i から i+1 に重み 2^(n-i-1) の辺を張り、i から i', i' から i+1 にそれぞれ重み 0 の辺を貼ると、 0 から n に 2^n 通りのパスがあり、どのパスの重みも異なるが、L(0, n) がこの全ての重みを降順に取るような緩和操作の順序が実現可能)。
実際には(多分教科書にも書いてある通り) Warshall-Floyd 法は三つ組を調べる順番も指定しており、この順序に従った場合「全ての三つ組を一度ずつ調べて〜」が正しくなりますが。
ありがとうございます。ワーシャルフロイド法については動画の中では軽く紹介しただけでしたので、突っ込んだコメントをいただけて嬉しく思います。ご指摘の通りワーシャルフロイド法はループを回す順番が決まっていて、i,j,kの三つ組をデタラメな順番で調べるのではなく「i→jはkを経由するほうが短くなるか」のkに関するループが一番外側に来るような順番で調べる必要があります。（だから(i,j,k)ではなく(k,i,j)という順で書くことが多いですね。）
ただ、ループを回す順番が間違っていたとしても、それを3回繰り返せば正しい答えが得られます。
Ikumi Hide, Soh Kumabe, Takanori Maehara: Incorrect implementations of the Floyd-Warshall algorithm give correct solutions after three repeats
arxiv.org/pdf/1904.01210.pdf
移動ロボットの経路計画でもダイクストラ法を見かけるのでとても参考になりました。
貴重な講義を公開してくださり、ありがとうございます！
ダイクストラ法とワーシャルフロイド法の説明ありがとうございました。
教科書だと抽象的で難しく感じる箇所も授業の具体例を見ることで、理解が早まりましたー。
ワーシャルフロイドわかりやすすぎる
在下第一次知道Dijkstra方法和Worshall-Floyd方法，谢谢早水先生🙏🏻
めちゃくちゃ分かりやすく、聞き取りやすいです
大変助かりました
アップロードありがとうございます！
社会に出てから数学の利便性を痛感しています笑
Well it was worth it learning japanese.
I was just reading up on Dijkstra and Bellman-Ford a couple minutes ago, and this lesson was a great way to supplement it
前に某有名先生のグラフ理論を受けたことがあるが全然わからなかった。今の若い先生はノリヨビ先生も含めて本当に授業が上手だ。
今７０，８０ぐらいの年代の大学の先生は授業がほんとに下手だった。（というかまったく準備していない。例外もいるけど）この某有名先生はけっこうナイーブな性格で自身によると
K大学で授業を抜け出そうとした生徒を運動場まで追いかけまわしたそうである（本人談）。先生の授業で私みたいな低能がなんかわかった気がする。
時間あればプログラム組みたい
確かにのりのいい先生ですけど正しくはヨビノリ先生ですね笑
アンパンマンと呼んでも喜ぶそうですが。
ダイクストラ法はITネットワークでも使われてますね！
ダイクストラ法において負の重みがネックになるのであれば、最小値分かそれ以上の値をすべての値について下駄をはかせてしまえば重みを非負値である条件下に強制的に持ってこれると思ったのですが駄目なのでしょうか？途中負値になることが許されないような状態を表すグラフではもちろん駄目だとはおもいますが
その場合、始点 -> 終点 までに何本の辺を通ったか、という情報が必要だと思いますが、ダイクストラ法によって求めた最短距離よりも、たくさん辺を通った最短距離よりも少し長い距離の方が距離が短くなる場合があります。例えば下駄が10だとして、ダイクストラ法によって答えは5 + 10*2と求められたけれども、実際は1 + 10*3の方が短いために最短距離が正しく求まりません（説明が下手で申し訳ないです）
快速とかあった場合には辺を増やせばいいですかね。
時刻表や乗り換え時間があった場合には重みで表現すればよいのかな。
動画で見るとそこまで難しい話をしていないのに教科書上で
言葉で説明しようとした途端に記号が増えてややこしく見える印象がありますね。
ワーシャルフロイド法について、重みが負である辺が存在する以上、自身から自身への最短経路の長さは0とは限らないのではないでしょうか。
コメントありがとうございます．一般に最短経路問題では，入力グラフにおいて「負閉路（重みの総和が負である閉路）」が無いと仮定されます．そのような閉路（あるいはループ）があったら，その負閉路をグルグル回り続けることで重みがいくらでも小さい経路を作れてしまい，重み最小の経路を考える意味がなくなるからです．
@@hayamizu 確かにそうですね。
ありがとうございます。
ダイクストラ法の説明は大変分かりやすくやはりこういうものは書籍よりも動画だなあと思います。早水先生の説明スキルも大変に高いのだと思います。ただ、ノートに落とそうとするととたんに困るんですね。私のノートには「ダイクストラ法 大変分かりやすかった」とのみ書いてあります。困ったらまた動画見よう。
ワーシャルフロイド法の方はノートにできる手順なんですけどね。面白いものです。
格納行列の成分を更新してどのように活用するのか気になります。
わざわざ行列にするということは、ただの参照用の表ではなく、行列の演算に活用するのだと思いますが。
中学生と高校生に塾のバイトで数学を教えている大学生です。
中学生の勉強が苦手な子に，「先生、数学って勉強して何に役立つの？算数だけで良くない？」と言われ、何も言い返せませんでした。このような場合、どのように答えるのが子供たちの学習意欲に繋がるのでしょうか、先生の意見をおきかせ願いませんでしょうか。
RUclipsにはそれに答えてくれる動画が沢山あるよと教えてあげてください😊
重み付きグラフを対象にしたクラスタリングまたはコミュニティ抽出のアルゴリズムや方法って何かあるのでしょうか．
グラフのラプラシアン行列を使ったスペクトラルクラスタリングといわれる方法がありますね．
people.csail.mit.edu/dsontag/courses/ml14/notes/Luxburg07_tutorial_spectral_clustering.pdf
@@hayamizu ありがとうございます
先生！Googleのヘッドハンターが一度お会いしたいって言ってました！
私は大学院生時代にGoogleから奨学金を頂いたので、Googleのオフィスには足を向けて寝られません。Googleにはとても感謝しています😊
Thanks!
SuperThanksありがとうございました！！🙏✨
分かりやすい講義ありがとうございます。ここから極限を取るとフェルマーの原理が導けるのでしょうか？
コメントありがとうございます。フェルマーの原理というのは、光は最短時間で通ることができる経路を進むという物理学の原理ですね。「ここから」とおっしゃっているのは何処からのことでしょうか？今回解説したのはグラフの中の最短経路を求めるための「計算方法」です。
早速の返信ありがとうございます。ダイクストラ法で頂点の数を増やし、辺の長さを短くしていけば、連続したシステムに近づいていき、媒体における光の最短経路なども計算することができると思います。一方、私が習った光の経路の解き方は変分法です。最終的な解はどちらも同じになると思うのですが、この変分法とダイクストラ法には何か関連があるのでしょうか？例えば微分法（連続）と差分法（離散）のような関係はあるのでしょうか？よろしくお願いします。的外れな質問でしたらすみません。
キャンパスで会ったら一緒に写真撮ってほしいです
写真ですか！？徹夜明けの日や寝坊して変な服装の日や時間に余裕がない日以外ならば良いですよ、見かけたら声かけてください😂