Dijkstra についての様々な変更

[ei1333]

Description

• SPFA などに仕様を合わせる
  • 関連 issue, PR

  • 110

  • 113

  • 適切に移動する
  • class の名前を変える
  • ドキュメントの計算量の $V$ や $E$ を $|V|$ や $|E|$ に変更する
• #pragma once を追加する
• <vector>, <functional> などの必要なヘッダーを適切に include する

Related files

• src/graph/dijkstra.hpp
• src/graph/single-source-shortest-path

note

[Luzhiled]

dijkstra くん問題だらけなので、移動に限らず様々やるべきですね

pragma once とかもだし、確か vector が使われているのに vector が include されていなかった

[Luzhiled]

class の名前も変える必要が

[ei1333]

https://github.com/luzhiled1333/comp-library/issues/65#issuecomment-1426393665

[ei1333]

src/graph/single-source-shortest-path/in-weighted-graph.hpp

[Luzhiled]

in-weighted-graph は Floyd-Warshall Algorithm っぽい

[ei1333]

そんな

[Luzhiled]

いや Floyd-Warshall は APSP だろ　Bellman-Ford Algorithm です

[ei1333]

では、どうしますか

[Luzhiled]

正の辺であることをかければいいんじゃないですか

[ei1333]

Dijkstraって負辺があると動かないんですね　今知りました

[Luzhiled]

負辺があっても動作するが、それは置いておいて positive-weighted とすると

[ei1333]

non-negative

[ei1333]

負辺があっても動作はするのか

[Luzhiled]

6年くらい前にらてくんがポテンシャルの話をしていた記憶があります　詳しいことは全然覚えていません

[ei1333]

ところで、SPFAというアルゴリズムはどうでしょう

[Luzhiled]

SPFA ではないでしょうか

[Luzhiled]

サイレント修正がきていた

[ei1333]

サイレント修正しました

[Luzhiled]

あ、これ Bellman-Ford より高速になりがちなんですね

[Luzhiled]

では issue を立てていただいて

[Luzhiled]

まともに読んでないからなんかよくわかんねえけどその手の話っぽいものはいくつか出てきた https://niuez.hatenablog.com/entry/2019/03/04/142903 https://qiita.com/ngtkana/items/d7fc4463e56b966d1ebf

[ei1333]

in-unweighted-graph.hpp、これを解くアルゴリズムが複数あるときに困ることに気が付きました

[Luzhiled]

いや、重みなしグラフの最短路は別に1つでよくないですか　他になにか亜種が出てくることありますかね

[Luzhiled]

亜種というのは、BFS では原理的に解けないグラフや、特殊なグラフにおいては BFS より真に高速になるようなものという意味ですね

[ei1333]

補グラフ最短路というのはどうだろう

[Luzhiled]

あーたしかに　まあそれは補グラフの最短路という名前になりそうだけど

[ei1333]

あ、これはAPSPでした

[ei1333]

特殊なグラフの場合はその名前をつければいいか

[Luzhiled]

まあそうなりそうな感じはあるよね

[Luzhiled]

Dijkstra は特殊なグラフで高速になる側だと思っていて、命名としてはそうなるのが適切かなと思います

[Luzhiled]

in-positive-weighted-graph でいいんじゃないかな

[Luzhiled]

ここにきてドキュメントの $|V|$ などが $V$ と表記されていることも発覚してきた

[ei1333]

$V$ は頂点集合を指したいですね

[Luzhiled]

description を更新しておきました

[Luzhiled]

description を更新しておきました3