Belief　Propagation　(BP),　a　distributed,　message-passing　algorithm,　has　been　widely　used　in　different　disciplines　including　information　theory,　artificial　intelligence,　statistics　and　optimization　problems　in　graphical　models　such　as　Bayesian　networks　and　Markov　random　fields.　Despite　BP　algorithm　has　a　great　success　in　many　application　fields　and　many　progress　about　BP　algorithm　has　been　made,　the　rigorous　analysis　about　the　correctness　and　convergence　of　BP　algorithm　are　known　in　only　a　few　cases　for　arbitrary　graph.　In　this　paper,　we　will　investigate　the　correctness　and　convergence　of　BP　algorithm　for　determining　the　optimal　solutions　of　the　Chinese　postman　problem　in　both　undirected　and　directed　graphs.　As　a　main　result,　we　prove　that　BP　algorithm　converges　to　the　optimal　solution　of　the　undirected　Chinese　postman　problem　within　O(n)　iterations　where　n　represents　the　number　of　vertices,　provided　that　the　optimal　solution　is　unique.　For　the　directed　case,　we　consider　the　directed　Chinese　postman　problem　with　capacity　and　show　that　BP　algorithm　also　converges　to　its　optimal　solution　after　O(n)　iterations,　as　long　as　its　corresponding　linear　programming　relaxation　has　the　unique　optimal　solution.