私と理論

数学の話を主に書きます

2019-09-08から1日間の記事一覧

二種類のDijkstra法とグラフの負辺

最近,最短路アルゴリズムについて新しく知ったことがあるのでメモ. 内容にそんなに自信はないので間違っているかも. グラフ 上の二点間の最短路問題と言えば 辺の長さが全て非負→Dijkstra法 負の長さの辺がある→Bellman-Ford法 というような使い分けを行…