一、多段圖問題

問題描述：設圖G=(V, E)是一個帶權有向圖，如果把頂點集合V劃分成k個互不相交的子集Vi (2≤k≤n, 1≤i≤k)，使得對于E中的任何一條邊(u, v)，必有u∈Vi，v∈Vi+m (1≤i≤k, 1＜i+m≤k)，則稱圖G為多段圖，稱s∈V1為源點，t∈Vk為終點。多段圖的最短路徑問題求從源點到終點的最小代價路徑。

二、抽象分析

設Cu-v表示多段圖的有向邊<u, v>上的權值，將從源點s到終點t的最短路徑長度記為d(s, t)，考慮原問題的部分解d(s, v)，顯然有下式成立：

d(s, v) =Cs-v?（<s, v>∈E）

d(s, v) = min{d(s, u) + Cu-v}? （<u, v>∈E）

1.循環(huán)變量j從1~n-1重復下述操作，執(zhí)行填表工作

?? 1.1考察頂點j的所有入邊，對于邊<i,j>∈E,執(zhí)行下述操作

?????? 1.1.1cost[j]=min{cost[i]+c[i][j]}；

?????? 1.1.2path[j]=使cost[i]+c[i][j]最小的i;

???? 1.2 j++;

2.輸出最短路徑長度cost[n-1]；

3.循環(huán)變量i=path[n-1].循環(huán)直到path[i]=0,輸出最短路徑經(jīng)過的頂點；

?? 3.1 輸出path[i];

?? 3.2 i=path[i]

三、例題具體分析

首先求解初始子問題，可直接獲得：

d(0, 1)=c01＝4(0→1)

d(0, 2)=c02＝2(0→2)

d(0, 3)=c03＝3(0→3)

再求解下一個階段的子問題，有：

d(0, 4)=min{d(0, 1)+c14, d(0, 2)+c24}=min{4+9, 2+6}=8(2→4)

d(0, 5)=min{d(0, 1)+c15, d(0, 2)+c25, d(0, 3)+c35}=min{4+8, 2+7, 3+4}?

?????????? =7(3→5)

d(0, 6)=min{d(0, 2)+c26, d(0, 3)+c36}=min{2+8, 3+7}=10(2→6)

再求解下一個階段的子問題，有：

d(0, 7)=min{d(0, 4)+c47, d(0, 5)+c57, d(0, 6)+c67}=min{8+5, 7+8, 10+6}

?????????? =13(4→7)

d(0, 8)=min{d(0, 4)+c48, d(0, 5)+c58, d(0, 6)+c68}=min{8+6, 7+6, 10+5}

?????????? =13(5→8)

直到最后一個階段，有：

d(0, 9)=min{d(0, 7)+c79, d(0, 8)+c89}=min{13+7, 13+3}=16(8→9)

再將狀態(tài)進行回溯，得到最短路徑0→3→5→8→9，最短路徑長度16。

（附輸入）

10 18
0 1 4
0 2 2
0 3 3
1 4 9
1 5 8
2 4 6
2 5 7
2 6 8
3 5 4
3 6 7
4 7 5
4 8 6
5 7 8
5 8 6
6 7 6
6 8 5
7 9 5
8 9 3

四、代碼

#include<iostream>
using namespace std;int vnum, arcnum;
int arc[100][100];
const int INT_MAX1 = 999;void printArc()
{cout << "鄰接矩陣為：" << endl;for (int i = 0; i < vnum; i++){for (int j = 0; j < vnum; j++){cout << arc[i][j] <<" ";}cout << endl;}cout << endl;
}int main()
{cin >> vnum >> arcnum;int i, j;//初始化鄰接矩陣，用999表示沒有邊f(xié)or (i = 0; i < vnum; i++){for (j = 0; j < vnum; j++){arc[i][j] = INT_MAX1;}}printArc();//輸入各邊while (arcnum--){int weight;cin >> i >> j >> weight;arc[i][j] = weight;}printArc();int cost[100] = { 0 };//記錄最小的代價int path[100] = { 0 };//記錄路徑，即經(jīng)過的頂點//初始化for (i = 1; i < vnum; i++){cost[i] = INT_MAX;path[i] = -1;}cost[0] = 0;path[0] = -1;//開始動態(tài)規(guī)劃，找出最小代價for (j = 1; j < vnum; j++){for (i = j - 1; i >= 0; i--){if (cost[i] + arc[i][j] < cost[j]){cost[j] = cost[i] + arc[i][j];path[j] = i;}}}// 輸出路徑i = vnum - 1;cout << i;while (path[i] >= 0) { // 前一個點大于0 cout << "<-" << path[i];i = path[i]; // 更新為前一個點 }cout << endl;cout << "最短路徑為：" << cost[vnum -1] << endl;system("pause");return 0;
}

?