最短路徑之迪傑斯特拉算法模闆(一)

最短路徑是圖論中一個很經典的問題：給定圖G(V，E)，求一條從起點到終點的路徑，使得這條路徑上經過的所有邊的邊權之和最小。即，對任意給出的圖G(V，E)和起點S、終點T，如何求從S到T的最短路徑。

這裡簡單說一下迪傑斯特拉算法(Dijkstra)解決單源點最短路徑問題，即給定圖G和起點S，通過算法得到S到達其它每個頂點的最短距離。

基本思想：

對圖G(V，E)設定集合S，存放已被通路的頂點，然後每次從集合V-S中選擇與起點s的最短距離最小的一個頂點(記為u)，通路并加入集合S。之後，令頂點u為中介點，優化起點s與所有從u能到達的頂點v之間的最短距離。這樣的操作執行n次(n為頂點個數)，直至集合S包含所有頂點。

因為圖可以用鄰接矩陣和鄰接表存儲，是以這裡打算将兩種方式都記錄一下。

（一）鄰接矩陣版的代碼(一般用于頂點數不超過1000)：

#include<iostream>
#include<algotithm>
//鄰接矩陣版 
const int maxn = 1000;	//最大頂點數，一般來說用鄰接矩陣則頂點數最好不超過1000 
const int INF = 1000000000;
int n, G[maxn][maxn];	//n為頂點數，G[u][v]表示頂點u到頂點v的距離 
int d[maxn];	//d[u]表示起點s到達u的距離
bool vis[maxn] = {false};	//vis[u]=false表示頂點u還未通路;反之則表示u已通路

//若需要輸出最短路徑上的每個頂點，則需用pre數組儲存
int pre[maxn];    //pre[v]表示從起點到頂點v的最短路徑上v的前一個頂點

void Dijkstra(int s){	//s是起點 
	//初始化
	fill(d, d + maxn, INF);
	d[s] = 0;	//起點s離起點距離為0
    for(int i = 0; i < n; i++) pre[i] = i;

	//執行n次操作 
	for(int i = 0; i < n; i++){	
		//1.先選擇離起點最近的 未被通路的 頂點u
		int u = -1, MIN = INF;
		for(int j = 0; j < n; j++){
			if(vis[j] == false && d[j] < MIN){
				u = j;
				MIN = d[j];
			}
		}
		//找不到小與INF的d[u]，說明剩下的頂點和起點s不連通 
		if(u == -1)	return;	

		//2. 通路u
		vis[u] = true;
			
		for(int v = 0; v < n; v++){
			//3.如果v未被通路 && u能到達v && 以u為中介點能優化d[v] 
			if(vis[v] == false && G[u][v] != INF && d[u] + G[u][v] < d[v]){
				d[v] = d[u] + G[u][v];	//優化起點到頂點v的距離
                pre[v] = u; 
			}
		} 
	} 
}
//輸出最短路徑上的每個頂點
void DFS(int s, int v){    //s是起點編号， v是目前通路的頂點編号(從終點開始遞歸)
    if(v == s){
        printf("%d\n", v);
        return;
    }
    DFS(s, pre[v]);
    printf("%d\n", v);
}
 
           

（二）鄰接表版的代碼：

#include<iostream>
#include<vector>
#include<algotithm>
//鄰接表版 
const int maxn = 1000;
const int INF = 1000000000;
struct Node{
	int v, dis;	//v是邊的目标頂點，dis是邊權 
};
int n;	//頂點數 
vector<Node> Adj[maxn];
int d[maxn];
bool vis[maxn] = {false};

void Dijkstra(int s){
	//初始化
	fill(d, d + maxn, INF);
	d[s] = 0;
	
	for(int i = 0; i < n; i++){	//執行n次操作 
		//選出距離起點最近的 未被通路的點
		int u = -1, MIN = INF;
		for(int j = 0; j < n; j++){
			if(vis[j] == false && d[j] < MIN){
				u = j;
				MIN = d[j];
			}
		}
		if(u == -1) return;
		vis[u] = true;
		//周遊與u相連的各個頂點 (和鄰接矩陣版的比，隻有下面代碼寫法稍有不同!!!)
		for(int j = 0; j < Adj[u].size(); j++){
			int v = Adj[u][j].v;	//與u相連的頂點編号是v 
			int dis = Adj[u][j].dis;	//u和v之間邊權是dis
			if(vis[v] == false && d[u] + dis < d[v]){
				d[v] = d[u] + dis;
			} 
		} 
	} 
} 
           

兩種形式代碼如上所示。仔細對比可以發現隻有少許不同。

仔細研究可以發現采用此模闆有些缺點：所求的最短路徑隻能是唯一一條，若有多條則不适用！！！