各ノードごとに (辺のコスト, その辺を使ったときの最長距離) を赤黒木で管理する.

辺を順に見ていき, 辺の始点側の赤黒木から辺のコストが見ている辺のコストを超えない最大の長さを取得し, 長さを1増やして辺の終点側の赤黒木に追加する.

辺の終点側の赤黒木では追加した辺のコスト以上で最長距離が今追加した最長距離より小さいものを削除する.