問題描述

物流問題

????????有一個(gè)物流公司需要從起點(diǎn)A到終點(diǎn)B進(jìn)行貨物運(yùn)輸，在運(yùn)輸過程中，該公司需要途徑多個(gè)不同的城市，并且在每個(gè)城市中都有一個(gè)配送站點(diǎn)。為了最大程度地降低運(yùn)輸成本和時(shí)間，該公司需要確定經(jīng)過哪些配送站點(diǎn)，并且給出完成貨物運(yùn)輸?shù)淖疃搪窂介L(zhǎng)度。

路線分布圖

問題分析

問題簡(jiǎn)化

????????可以將該問題抽象為多段圖的最短路徑問題，其中每個(gè)城市對(duì)應(yīng)圖中的一個(gè)節(jié)點(diǎn)，不同城市之間的距離對(duì)應(yīng)著圖中的邊權(quán)，城市內(nèi)部的配送站可以看作同一個(gè)節(jié)點(diǎn)。從起點(diǎn)A到終點(diǎn)B的貨物運(yùn)輸路徑可以表示為多段圖中的一條路徑。找到起點(diǎn)A到終點(diǎn)B的最短路徑并給出路徑長(zhǎng)度即可求解此問題。

路線簡(jiǎn)化圖

多段圖最短路徑的填表

下標(biāo)	1	2	3	4	5	6	7	8	9
元素值	4	8	6	10	8	12	14	17	15
狀態(tài)轉(zhuǎn)換	0->1	0->2	0->3	1->4	3->5	5->6	5->7	5->8	7->9

最短路徑為：0->3->5->7->9，最短路徑長(zhǎng)度為15

算法設(shè)計(jì)

算法設(shè)計(jì)分析

????????多段圖的最短路徑問題滿足最優(yōu)性原理，可以使用動(dòng)態(tài)規(guī)劃法求解。

????????設(shè)Cuv表示多段圖的有向邊<u,v>上的權(quán)值，從源點(diǎn)s到終點(diǎn)t的最短路徑長(zhǎng)度記為d(s,t)，原問題的部分解d(s,v)，則下式成立：

d(s,v)=Csv ???????????????(<s,v>∈E)

d(s,v)=min{d(s,u)+Cuv} ????(<u,v>∈E)

數(shù)組arc[n][n]存儲(chǔ)圖的代價(jià)矩陣，數(shù)組cost[n]存儲(chǔ)最短路徑長(zhǎng)度，cost[j]表示從源點(diǎn)s到頂點(diǎn)j的最短路徑長(zhǎng)度，數(shù)組path[n]記錄轉(zhuǎn)移狀態(tài)，path[j]表示從源點(diǎn)s到頂點(diǎn)j的路徑上頂點(diǎn)j的前一個(gè)頂點(diǎn)。

算法偽代碼

輸入：多段圖的代價(jià)矩陣

輸出：最短路徑長(zhǎng)度及路徑c[n][n]

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

??1.1考察頂點(diǎn)j的所有入邊，對(duì)于邊<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.輸出最短路徑長(zhǎng)度cost[n-1]

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

??3.1輸出path[i]

??3.2 i=path[i]

實(shí)驗(yàn)結(jié)果

最短路徑

最短路徑為：0->3->5->7->9，最短路徑長(zhǎng)度是15

算法分析

時(shí)間復(fù)雜度分析

????????算法第一部分是依次計(jì)算從源點(diǎn)到各個(gè)頂點(diǎn)的最短路徑長(zhǎng)度，由兩層循環(huán)嵌套組成，外層循環(huán)執(zhí)行n-1次，內(nèi)層循環(huán)對(duì)所有入邊進(jìn)行計(jì)算，在所有循環(huán)中，每條入邊只計(jì)算一次。假設(shè)圖的邊數(shù)為m，時(shí)間復(fù)雜度為O(m)；第二部分是輸出最短路徑經(jīng)過的頂點(diǎn)，設(shè)多段圖劃分為k段，時(shí)間復(fù)雜度為O(k)。整個(gè)算法的時(shí)間復(fù)雜度為O(m+k)。

空間復(fù)雜度分析

????????算法的空間復(fù)雜度主要體現(xiàn)在圖的代價(jià)矩陣arc[n][n]的存儲(chǔ)，空間復(fù)雜度為O(n^2),存儲(chǔ)最短路徑長(zhǎng)度的數(shù)組cost[n]的空間復(fù)雜度為O(n)，轉(zhuǎn)移狀態(tài)記錄數(shù)組path[n]的空間復(fù)雜度為O(n)，所以整個(gè)算法的空間復(fù)雜度為O(n^2)。

源代碼

#include<iostream>
using namespace std;
#define INF 999
int arc[10][10]; // 最多10個(gè)點(diǎn) 
int CreateGraph()
{int i, j, k;int weight;int vnum, arcnum;cout << "請(qǐng)輸入頂點(diǎn)和邊的個(gè)數(shù)：";cin >> vnum >> arcnum;for (int i = 0; i < vnum; i++) 	// 初始化圖的代價(jià)矩陣 for (int j = 0; j < vnum; j++)arc[i][j] = INF;for (k = 0; k < arcnum; k++){cout << "請(qǐng)輸入第" << k + 1 << "條邊的兩個(gè)頂點(diǎn)和權(quán)值：";cin >> i >> j >> weight;arc[i][j] = weight;}return vnum;  // 返回頂點(diǎn)的個(gè)數(shù)
}
// 求 n個(gè)頂點(diǎn)的多段圖的最短路徑 
int BackPath(int n)
{int i, j, temp;int cost[100], path[100]; // 存儲(chǔ)路徑長(zhǎng)度和路徑 for (i = 1; i < n; i++){cost[i] = INF;path[i] = -1;}cost[0] = 0;			// 頂點(diǎn)0為源點(diǎn) path[0] = -1;for (j = 1; j < n; j++)		// 依次計(jì)算后面下標(biāo)為1到n-1的點(diǎn)（填表） 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;			// 記錄前一個(gè)點(diǎn) }}// 輸出路徑i = n - 1;cout << "最短路徑為：" << i;while (path[i] >= 0)// 前一個(gè)點(diǎn)大于0 {cout << "<-" << path[i];i = path[i]; // 更新為前一個(gè)點(diǎn) }cout << endl;return cost[n - 1]; // 返回最短路徑長(zhǎng)度 
}
int main()
{int graph = CreateGraph();cout << "最短路徑長(zhǎng)度為：" << BackPath(graph) << endl;return 0;
}

感謝大家的觀看