中国人郵便配達問題
この組のそれぞれについて、「最短経路を見つけ、その辺をそれぞれ1本増やす」ことを行う。
よって中国人郵便配達問題は、上記の手順2における頂点を二つずつ組み合わせる方法のうち、手順3にて増やす辺の距離を最小にするようなものを求める問題(最小マッチング)に帰着される。この最小マッチングは O ( V 3 ) {\displaystyle O(V^{3})} 時間で求められることが知られている(ただし、そのアルゴリズムは難しいものである)。他の処理も O ( V 3 ) {\displaystyle O(V^{3})} 時間以内で行えるため(全頂点組に対する最短経路を見つけることはワーシャル-フロイド法により O ( V 3 ) {\displaystyle O(V^{3})} 時間で可能)、全体の時間計算量も O ( V 3 ) {\displaystyle O(V^{3})} となる。ただし、 V {\displaystyle V} は頂点の数である。