全辺巡回・郵便配達問題

すべての辺を少なくとも1回通って始点に戻る最小費用の経路を求める。

対象は無向・連結のネットワークの閉巡回です。各辺のコストは0以上、小数第6位までです。

厳密計算は最大120辺・80頂点・奇数次数16頂点です。上限を超える場合は最適値を示しません。

項目を入力・選択してから「計算する」を押してください。

必要な入力・選択は2項目です。

対象辺(無向)必須
行辺ID端点A端点Bコスト操作
1

4列を左端の欄へタブ区切りで貼り付けられます。120行まで。

1行が1本の辺です。多重辺は別々の辺IDで入力します。自己ループも指定できます。表の最後の空行は計算対象外です。コストはすべて同じ単位で入力してください。

辺の端点にある頂点IDを指定します。終点は同じ頂点です。


計算結果

値を入力して計算してください。

お気に入り一覧

計算方法・適用範囲・出典

計算方法

元費用C=Σ辺コスト。次数が奇数の頂点を抽出し、頂点間の重み付き最短距離を計算。奇数次数頂点の最小費用完全マッチングで得た各ペアの最短路を複製し、追加費用Mを得ます。すべて偶数次数となった多重グラフでEuler巡回を構築し、全ての元の辺IDが1回以上現れること、始点に戻ること、費用C+Mであることを検査します。0費用・多重辺・自己ループを含みます。

辺ID付きの閉巡回、再走行する辺、元・追加・総コスト。

計算例(架空の数値)

3頂点A・B・Cの三角形で辺AB、BC、CAが各1なら最小費用3で各辺を1回ずつ通ります。辺ABだけで費用5ならA→B→Aで総費用10です。

適用対象と限界

全ての対象辺と非負費用が分かり、各辺を両方向に通れる小規模な無向ネットワーク。有向辺・一方通行・時間/車両/容量制約・非連結成分の移動補完・実際の道路通行可否・16個超の奇数次数頂点に対する最適性判定。

採用した方式

  • 重み付き最小費用完全マッチング(厳密DP)(v1.0):対象範囲 連結無向、辺120本・頂点80個・奇数次数頂点16個以下、閉巡回/適用地域 global

方法と出典

方法:E1221 undirected-weighted-cpp exact bitmask-dp v1.0。データ記録日:2026-11-14。