Japanese subtitles

← 05-22 All Pairs Shortest Paths

Get Embed Code
3 Languages

Showing Revision 1 created 03/11/2014 by Fran Ontanaya.

  1. ソーシャルネットワークで中心となるノードの見つけ方を
    前レッスンで学びました
  2. とあるノードが他のノードからどれだけ
  3. 離れているか調べ値を得ます
  4. こうやってノード同士の距離を調べていきます
  5. 知りたいのはノード間の最短距離です
  6. すべてのノードペアについてです
  7. これでみなさん最短経路の計算を
    m log n時間で実行できますね
  8. ではすべてのノードからダイクストラ法の計算を
  9. 繰り返してみましょう
  10. すると頂点数×n log nの計算時間で全頂点間の距離を
  11. 計算することができます
  12. このグラフがどの程度の密度の高さかにより
    実際の計算時間は変わってきます
  13. 連結グラフで密度が低い場合mはnと同じなので
  14. グラフの密度が高い場合は頂点の数の2乗になります
  15. したがって実行時間は
  16. n³×log nとなります
  17. フィボナッチヒープの概念を使えば少しよい結果が出る
  18. 可能性もありますが現実的に実装可能なコードとしては
  19. 最善と思われます しかしこれを上回る
  20. 方法があるのです