設(shè)G=(V,E)是一個(gè)賦權(quán)有向圖,其頂點(diǎn)集V被劃分成k>2個(gè)不相交的子集Vi:1≤i≤k,其中,V1和Vk分別只有一個(gè)頂點(diǎn)s(稱為源)和一個(gè)頂點(diǎn)t(稱為匯),圖中所有的邊(u,v),u∈Vi,v∈Vi+1。求由s到t的最小成本路徑。 a)給出使用動(dòng)態(tài)規(guī)劃算法求解多段圖問(wèn)題的基本思想。 b)使用上述方法求解如下多段圖問(wèn)題。