例51[多段图问题]多段图G=(vE是一个有向图,且具有特:°° 性 ●●0 ●●●● 结点:结点集V被分成k≥2个不相交的集合V 1≤i≤k 其中V1和V分别只有一个结点s(源点)和t(汇点) 每一集合V定义图中的一段。 边:所有的边(u,V)均具有如下性质:若<u,v>∈E 则该边将是从某段指向+1段,即若u∈V1,则v∈V1+y ≤i≤k-1 每条边(u,v)均附有成本c(u,v)。 s到t的路径:从第1段开始,至第2段、第3段、…、最后 在第k段终止。路径的成本是这条路径上边的成本和。 多段图问题:求由s到t的最小成本路径。2021/2/8 例5.1 [多段图问题]多段图G=(V,E)是一个有向图，且具有特 性: 结点：结点集V被分成k≥2个不相交的集合Vi， 1≤i≤k， 其中V1和Vk分别只有一个结点s(源点)和t(汇点) · 每一集合Vi定义图中的一段。 边： 所有的边(u,v)均具有如下性质： 若<u,v>∈E， 则该边将是从某段i指向i+1段，即若u∈Vi，则v∈Vi＋1, 1≤i≤k－1。 · 每条边(u,v)均附有成本c(u,v)。 s到t的路径：从第1段开始，至第2段、第3段、…、最后 在第k段终止。路径的成本是这条路径上边的成本和。 多段图问题：求由s到t的最小成本路径