Spaghetti Source - 全点対間最短路 (Floyd Warshall)
説明 Floyd Warshall は隣接行列形式で与えられたグラフの全点対間最短路を求めるアルゴリズムである．負閉路が存在する場合はそれも検出する． アルゴリズムは次の通り．これまでに得られている始点 i から終点 j までの最短路を d[i][j] とするとき，ある頂点 k が存在して d[i][j] > d[i][k] + d[k][j] のとき d[i][j] を更新する．これを k を 1 から n まで増加させながら実行する．これにより，k 番目のループにおける d[i][j] は高々 k 番目の頂点までを中継点に用いる最短経路となって，動的計画法に基づくアルゴリズムが完成する．なお，d[i][i] < 0 のときは i を含む負閉路があることがわかる． このアルゴリズムは，本質的にはグラフの二点対 i,j について，その間のすべての経路にわたる経路積の和を計算するものである．
Toriumi Lab.
2024年3月26日 「情報的健康プロジェクト：アテンションエコノミーの暗翳と『情報的健康』−総合知で創出する健全な言論空間」を慶應義塾大&オンラインで開催されました. https://www.kgri.keio.ac.jp/news-event/156808.html 査読付き論文が出版されました．Chujyo, M., Toriumi, F. "Link-limited bypass rewiring for enhancing the robustness of complex networks". Appl Network Science Vol.9, No.17 (2024). (2024年5月) 査読付き論文が出版されました．Lai, C., Toriumi, F. & Yoshida, M. ”A multilingual analysis of pro Russian m
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
c3-02.PDF
