As　an　algorithmic　framework,　message　passing　is　extremely　powerful　and　has　wide　applications　in　the　context　of　different　disciplines　including　communications,　coding　theory,　statistics,　signal　processing,　artificial　intelligence　and　combinatorial　optimization.　In　this　paper,　we　investigate　the　performance　of　a　message-passing　algorithm　called　min-sum　belief　propagation　(BP)　for　the　vertex-disjoint　shortest　k　-path　problem　(　k　-VDSP)　on　weighted　directed　graphs,　and　derive　the　iterative　message-passing　update　rules.　As　the　main　result　of　this　paper,　we　prove　that　for　a　weighted　directed　graph　G　of　order　n　,　BP　algorithm　converges　to　the　unique　optimal　solution　of　k　-VDSP　on　G　within　O(n{2}w_{max})　iterations,　provided　that　the　weight　w_{e}　is　nonnegative　integral　for　each　arc　ein　E(G)　,　where　w_{max}=max　{w_{e}:　ein　E(G)}.　To　the　best　of　our　knowledge,　this　is　the　first　instance　where　BP　algorithm　is　proved　correct　for　NP-hard　problems.　Additionally,　we　establish　the　extensions　of　k　-VDSP　to　the　case　of　multiple　sources　or　sinks.　©　1963-2012　IEEE.