iwiwi 備忘録

学んだことを殴り書きます。自分向けのメモです。

2013-12-26から1日間の記事一覧

Finding the k Shortest Paths (SICOMP'98)

s, t が与えられるので,k 本の最短路を計算する O(m + n log n + k) でできるよっていう論文 キーとなるアイディア t からの逆最短路木を T とする 例によって,ポテンシャルを使って辺の重みを変換する.T に含まれる辺の重みは 0 になる. パス p は,T …