前言

資料結構，一門資料處理的藝術，精巧的結構在一個又一個演算法下發揮著他們無與倫比的高效和精密之美，在為資訊技術打下堅實地基的同時，也令無數開發者和探索者為之著迷，

也因如此，它作為博主大二上學期最重要的必修課出現了，由于大家對于上學期C++系列博文的支持，我打算將這門課的筆記也寫作系列博文，既用于整理、消化，也用于同各位交流、展示資料結構的美，

此系列文章，將會分成兩條主線，一條“資料結構基礎”，一條“資料結構拓展”，“資料結構基礎”主要以記錄課上內容為主，“拓展”則是以課上內容為基礎的更加高深的資料結構或相關應用知識，

歡迎關注博主，一起交流、學習、進步，往期的文章將會放在文末，

隨著學習的深入，相信各位讀者的野心已經僅滿足于計算出任意兩點間的最短路徑，那么更進一步的，在這一節我們要討論關于最短路徑的計數問題，在計算出任意兩點間的最短路徑長度的基礎上，我們還需要統計出這些最短路徑的方案數，

這個問題，乍一看感覺有些不同尋常，因為不管怎么說，方案數相較于長度來說總還是不好把握的，我們在思考統計方案數的演算法的時候總是容易囿于對起點到終點路徑規劃決策的模擬，

樸素的解決思路多是先在紙上推演從一起點到終點的路徑，一條一條的畫出最短路徑，小規模的時候，找出答案不是難事，但是一旦資料量較大，筆算就會漏洞百出，更何況一旦準備將其付諸于程式，就像是秀才遇到兵，發現根本無從下手，，，，
在這里插入圖片描述
所以解決問題的關鍵就是要跳出樸素的思維方式，用一種新的視角來審視這個問題，不妨先從回顧計算最短路徑長度的演算法開始，

floyd演算法求最短路徑

任意兩點間的最短路徑問題，解決的方案是選擇不停地列舉中間點來對路徑進行“松弛”，讓各點之間不斷挑選更優的路徑從而將距離邊的更短，

如下圖，對于點對14來說，可以經由中間點2，走1->2->4這條更短的路徑，
在這里插入圖片描述

當然，能用來更新最短路徑的中間點也可以不是直接相連的頂點，例如下圖：
在這里插入圖片描述
點對15的最短路徑可能由3更新成為5，不過在此之前，13和35的距離應該分別被2和4更新成為2.

可以看到，在這個問題中，有個關鍵的狀態定義，點對 ( i , j ) (i,j) (i,j)之間的最短路徑長度 d i j d_{ij} dij?，

這個定義讓我們只關心點與點之間的路徑長度關系而非具體路徑，

進一步的，根據這個狀態定義，可以找到狀態間轉移方案：經過中間點k的點對ij的最短路徑就是：
d i j = m i n ( d i k + d k j , d i j ) d_{ij}=min(d_{ik}+d_{kj},d_{ij}) dij?=min(dik?+dkj?,dij?)
那么在演算法的初始，將最短路徑長度初始化：
d i i = 0 d_{ii}=0 dii?=0
d i j = i n f ( i j 之間沒有邊相連 ) d_{ij}=inf\ (ij之間沒有邊相連) dij?=inf (ij之間沒有邊相連)
d i j = l e n i j ( i j 之間有長度為 l e n i j 的邊鏈接 ) d_{ij}=len_{ij}\ (ij之間有長度為len_{ij}的邊鏈接) dij?=lenij? (ij之間有長度為lenij?的邊鏈接)

于是這個最短路徑長度的演算法問題就可以解了，步驟如下：

依次列舉所有中間節點k，更新其余點對
列舉非中間節點的點對ij
使用中間節點k對ij之間的最短路徑長度進行松弛

代碼實作如下：

int dis[N][N];//最短路徑陣列,ij最短路徑為dis[i][j]
void floyd(int n){
	for(int k = 1;k <= n;k++){//列舉中間節點
		for(int i = 1;i <= n;i++){//列舉非中間節點的點對
			if(i == k)continue;
			for(int j = i + 1;j <= n;j++){
				if(j == k)continue;
				if(dis[i][j] > dis[i][k] + dis[k][j]){//松弛最短路徑
					dis[i][j] = dis[i][k] + dis[k][j];
					dis[j][i] = dis[i][k] + dis[k][j];
				}
			}
		}
	}
}

兩點間最短路徑方案數

要統計最短路徑的方案數，沒有最短路徑長度肯定是不行的，所以以下的演算法要建立在floyd演算法之上，也就是說，方案數問題要在floyd的程序中順手解決

前面說過，要解決最短路徑的方案數統計問題，我們要跳出樸素的思維方案，借鑒最短路徑長度的建模分析方法，

不知各位是否注意到了上文在分析最短路徑演算法時標記出了三個模塊，他們分別是：
狀態、轉移、初始化狀態、轉移、初始化狀態、轉移、初始化這是解決路徑長度問題的關鍵所在，也就是常常提到floyd用到的動態規劃思想，

現在我們可以從動態規劃的角度借助這三個模塊依葫蘆畫瓢來分析最短路徑方案數的問題，（當然這里對狀態和轉移的描述未必在學術上嚴謹，主要是便于分析解決問題，）

定狀態

依照最短路徑的狀態 d i j d_{ij} dij?，我們定義：
點對 ( i , j ) 之間的最短路徑方案數 = c i j 點對(i,j)之間的最短路徑方案數=c_{ij} 點對(i,j)之間的最短路徑方案數=cij?(c取自count單詞首字母)

有了這個定義，在任意兩點間最短路方案數方面，用一個狀態便可以忽略具體的路徑方案，將方案數量一言以蔽之，

找轉移

定義了狀態之后，我們迫切的想知道在使用中間點k松弛點對ij時，最短路徑的方案數狀態會如何轉移，

首先一點，路徑的計算應該滿足乘法原理，即：
點對 ( i , j ) 經過點 k 的最短路徑方案數 = c i k × c j k 點對(i,j)經過點k的最短路徑方案數=c_{ik}\times c_{jk} 點對(i,j)經過點k的最短路徑方案數=cik?×cjk?
舉個例子，如下圖：
在這里插入圖片描述

對于中間節點4，點對17之間的最短路徑方案數為 2 × 2 = 4 2\times2=4 2×2=4（14方案數為2,47方案數為2）

乘法原理這里很好理解，就不再贅述了，下面的問題就是在進行floyd演算法程序中，計算出來的方案數要怎么進行轉移，這個問題要拆成三種情況來討論：

當經過k不能使得i到j已知路徑更短，即 d i j < d i k + d k j d_{ij} < d_{ik}+d_{kj} dij?<dik?+dkj?，此次松弛無效，不改變方案數 c i j c_{ij} cij?
當經過k的最短路徑長度等于已知路徑長度，即 d i j = d i k + d k j d_{ij} = d_{ik}+d_{kj} dij?=dik?+dkj?，i到j的方案應該加上從k走的方案數，即 c i j = c i j + c i k × c k j c_{ij}=c_{ij}+c_{ik}\times c_{kj} cij?=cij?+cik?×ckj?
當經過k的最短路徑長度小于已知路徑長度，即 d i j > d i k + d k j d_{ij} > d_{ik}+d_{kj} dij?>dik?+dkj?，i到j之前的方案應該作廢而只算從k走的方案數，即 c i j = c i k × c k j c_{ij}=c_{ik}\times c_{kj} cij?=cik?×ckj?

于是，狀態轉移的問題也就解決了

初始化

方案數的初始化方法就是給每個有邊的點對之間只能通過這條邊到達，方案數置1，否則不能到達，置0

實作

有了上面的鋪墊，下面就可以大刀闊斧的開始計算最短路徑的方案數了，

步驟如下：

初始化方案數矩陣
執行floyd演算法，在松弛程序中同時轉移方案數
1. 當經過k不能使得i到j已知路徑更短，即 d i j < d i k + d k j d_{ij} < d_{ik}+d_{kj} dij?<dik?+dkj?，此次松弛無效，不改變方案數 c i j c_{ij} cij?
1. 當經過k的最短路徑長度等于已知路徑長度，即 d i j = d i k + d k j d_{ij} = d_{ik}+d_{kj} dij?=dik?+dkj?，i到j的方案應該加上從k走的方案數，即 c i j = c i j + c i k × c k j c_{ij}=c_{ij}+c_{ik}\times c_{kj} cij?=cij?+cik?×ckj?
1. 當經過k的最短路徑長度小于已知路徑長度，即 d i j > d i k + d k j d_{ij} > d_{ik}+d_{kj} dij?>dik?+dkj?，i到j之前的方案應該作廢而只算從k走的方案數，即 c i j = c i k × c k j c_{ij}=c_{ik}\times c_{kj} cij?=cik?×ckj?

實作起來也不難，改動一下上文的代碼：

int dis[N][N];//最短路徑長度矩陣
int cnt[N][N];//最短路徑計數矩陣
void floyd(int n){
	for(int k = 1;k <= n;k++){//列舉中間節點
		for(int i = 1;i <= n;i++){//列舉非中間節點點對
			if(i == k)continue;
			for(int j = i + 1;j <= n;j++){
				if(j == k)continue;
				if(dis[i][j] == dis[i][k] + dis[k][j]){//當經過中間點最短距離相等，方案數相加
					cnt[i][j] += cnt[i][k] * cnt[k][j];
					cnt[j][i] += cnt[i][k] * cnt[k][j];
				}else if(dis[i][j] > dis[i][k] + dis[k][j]){//當經過中間點最短距離更小，之前方案數歸零，計經過k的方案數
					dis[i][j] = dis[i][k] + dis[k][j];
					dis[j][i] = dis[i][k] + dis[k][j];
					cnt[i][j] = cnt[i][k] * cnt[k][j];
					cnt[j][i] = cnt[i][k] * cnt[k][j];
				}
			}
		}
	}
}

讓我們來擬定一個需求，測驗這個場景：

給定n個頂點和m條邊，求出任意兩點間的最短路徑長度和方案數

#include<iostream>
using namespace std;
int dis[105][105];
int cnt[105][105];
const int inf = 1 << 29;

void floyd(int n){
	for(int k = 1;k <= n;k++){//列舉中間節點
		for(int i = 1;i <= n;i++){//列舉非中間節點點對
			if(i == k)continue;
			for(int j = i + 1;j <= n;j++){
				if(j == k)continue;
				if(dis[i][j] == dis[i][k] + dis[k][j]){//當經過中間點最短距離相等，方案數相加
					cnt[i][j] += cnt[i][k] * cnt[k][j];
					cnt[j][i] += cnt[i][k] * cnt[k][j];
				}else if(dis[i][j] > dis[i][k] + dis[k][j]){//當經過中間點最短距離更小，之前方案數歸零，計經過k的方案數
					dis[i][j] = dis[i][k] + dis[k][j];
					dis[j][i] = dis[i][k] + dis[k][j];
					cnt[i][j] = cnt[i][k] * cnt[k][j];
					cnt[j][i] = cnt[i][k] * cnt[k][j];
				}
			}
		}
	}
}

int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	
	for(int i = 1;i <= n;i++){//初始化距離和計數矩陣
		for(int j = 1;j <= n;j++){
			dis[i][j] = inf;
			cnt[i][j] = 0;
		}
		dis[i][i] = 0;
	}
	
	for(int i = 0,x,y,l;i < m;i++){//讀入m條邊
		scanf("%d%d%d",&x,&y,&l);
		dis[x][y] = l;
		dis[y][x] = l;
		cnt[x][y] = 1;
		cnt[y][x] = 1;
	}
	
	floyd(n);//floyd演算法計算長度和計數
	
	/*列印長度資訊和計數資訊*/
	printf("最短路徑長度矩陣：\n");
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= n;j++){
			printf("%-3d",dis[i][j] == inf ? -1 : dis[i][j]);
		}
		printf("\n");
	}
	printf("最短路徑計數矩陣：\n");
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= n;j++){
			printf("%-3d",cnt[i][j]);
		}
		printf("\n");
	}
}

進行一個測驗樣例：
在這里插入圖片描述

經過指定頂點的最短路徑數

好的，現在經過改進過的floyd演算法，我們可以統計出任意兩點間的最短路徑數量了，那么接下來我們還想知道另一個問題：如何統計兩點間經過指定中間頂點的最短路徑方案數

其實有了前面的鋪墊，這個問題就變得很簡單，我們模仿上面的套路，不妨先給個狀態定義：
點對 ( i , j ) 之間經過中間頂點 k 的最短路徑方案數 = c i j k 點對(i,j)之間經過中間頂點k的最短路徑方案數=c_{ij}^k 點對(i,j)之間經過中間頂點k的最短路徑方案數=cijk?

那么狀態的轉移如下：

當ij之間存在經過k的最短路徑，有 d i j = d i k + d k j d_{ij} =d_{ik}+d_{kj} dij?=dik?+dkj?，方案數 c i j k = c i k × c k j c_{ij}^k=c_{ik}\times c_{kj} cijk?=cik?×ckj?（還記的上文的乘法原理嗎？）
當ij之間不存在經過k的最短路徑，即 d i j < d i k + d k j d_{ij} <d_{ik}+d_{kj} dij?<dik?+dkj?，方案數 c i j k = 0 c_{ij}^k=0 cijk?=0

于是乎這個問題就解決了~

往期博客

【資料結構基礎】資料結構基礎概念
【資料結構基礎】線性資料結構——線性表概念及陣列的封裝
【資料結構基礎】線性資料結構——三種鏈表的總結及封裝
【資料結構基礎】線性資料結構——堆疊和佇列的總結及封裝(C和java)
【演算法與資料結構基礎】模式匹配問題與KMP演算法
【資料結構與演算法基礎】二叉樹與其遍歷序列的互化附代碼實作（C和java）
【資料結構與演算法拓展】單調佇列原理及代碼實作
【資料結構基礎】圖的存盤結構
【資料結構與演算法基礎】并查集原理、封裝實作及例題決議（C和java）
【資料結構與演算法拓展】二叉堆原理、實作與例題（C和java）
【資料結構與演算法基礎】哈夫曼樹與哈夫曼編碼(C++)
【資料結構與演算法基礎】最短路徑問題
【資料結構與演算法基礎】堆排序原理及實作
【資料結構與演算法基礎】最小生成樹演算法原理及實作
【資料結構基礎】圖的遍歷方法與應用
【資料結構基礎】矩陣的存盤結構，陣列，三元組表及十字鏈表
【資料結構與演算法基礎】拓撲排序與AOV網路
【資料結構與演算法基礎】AOE網路與關鍵路徑
【資料結構與演算法基礎】樹與二叉樹的互化

參考資料：

《資料結構》（劉大有，楊博等編著）
《演算法導論》（托馬斯·科爾曼等編著）
《圖解資料結構——使用Java》（胡昭民著）
OI WiKi

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/235535.html

標籤：其他

上一篇：第三屆泰迪杯技能賽賽后分享總結

下一篇：C++高并發網路架構與實作——第五篇

【資料結構與演算法拓展】最短路徑的方案數統計問題（基于floyd演算法）

前言