货郎担问题属于易于描述但难于解决的著名难题之一，至今世界上还有不少人在研究它。该问题的基本描述是：某售货员要到若干个村庄售货，各村庄之间的路程是已知的，为了提高效率，售货员决定从所在商店出发，到每个村庄售一次货然后返回商店，问他应选择一条什么路线才能使所走的总路程最短此问题可描述如下：设g=(v，e)是一个具有边成本cij的有向图，cij的定义如下，对于所有的i和j,cij>0，若
g(1，v一{1})是一条最优的周游路线长度。于是可以得出
g(1，v一{1))＝{clk十g(k，v一{1,k}))
将(4．19)式一般化可得
g(i，s)—{cij+g(j，s—{j})}(4．20)
例17考虑图4。13(a)，其边长由图4.13(b)中的矩阵c给出：
g(2，∮)＝c2l=5g(3，∮)=c31＝6g(4，∮)=c41＝8
由(4．20)式得
g(2，{3})=c23+g(3，∮)=15g(2，{4})＝18
g(4，{2}=13g(4，{3})=15
g(2，{3，4})=min{c23+g(3，{4})，c24+g(4，{3})=25
g(3，{2，4})＝min{c322+g(2，{4})，c34+g(4，{2})}＝25
g(4，{2，3})＝min{c422+g(2，{3})，c42+g(3，{2})}＝23
最后，由(19)式得
g(1，{2，3，4})＝min{c12-g(2，{3，4})，c13+g(3，{2，4})，c14+g(4，{2，3})}＝min{35，40，43}=35
图13(a)中的这个有向图的最优周游路线长度为35。如果对每个g(i，s)，保留使(20)
式右边取最小值的那个j值，那末就可构造出这一最优周游路线。令j(i，s)是这个值，则j(1，{2，3，4})=2。它表示这条周游路线由1开始并通到2。剩下的路径可由g(2，{3，4})得到。因j(2，{3，4})＝4，故这下一条边是(2，4)。以后的剩余段由g(4，{3})来获得j(4，{3})=3。因此这条最优周游路线是1，2，4，3，l。