最短路徑---Dijkstra算法（單源+邊權非負數）

Dijkstra算法（迪傑斯特拉算法）用來解決單源最短路問題

如果邊權出現負數，用SPFA 算法
           

可以用STL的優先隊列priority_queue來優化

Dijkstra僞代碼：

//G為圖，一般設為全局變量，數組d為源點到達各點的最短路徑長度，s為起點

Dijkstra(G,d[],s){
	初始化;
	for(循環n次){
		u=使d[u]最小的還未被通路的頂點的标号;
		記u已被通路;
		for(從u出發能到達的所有頂點v){
			if(v未被通路&&以u為中介點使s到頂點v的最短距離d[v]更優){
				優化d[v]; 
			}
		} 
	} 
} 
           

鄰接矩陣版

• 适合點數<=1000的情況

int n;G[maxn][maxn];
int d[maxn];
bool vis[maxn]={false};

void Dijkstra(int s){ //s為起點 
	fill(d,d+maxn,INF);
	d[s]=0;//起點s到達自身的距離為0 
	for(int i=0;i<n;i++){
		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 ;
		vis[u]=true;
		for(int v=0;v<n;v++){
			if(vis[v]==false&&G[u][v]!=INF&&d[u]+G[u][v]<d[v])
			d[v]=d[u]+G[u][v];
		}
	}
	
}
           

鄰接表版：

struct Node{
	int v,dis;//v為邊的目标頂點，dis為邊權 
};
vector<Node> Adj[maxn];
int n;
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++){
		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;
		for(int j=0;j<Adj[u].size();j++){
			int v=Adj[u][j].v;
			if(vis[v]==false&&d[u]+Adj[u][j].dis<d[v]){
				d[v]=d[u]+Adj[u][j].dis;
			}
		}
	}
}
           

最短路徑：

設定pre[],令pre[v]表示從起點s到頂點v的最短路徑上v的前一個頂點（即前驅結點）

在if内加一行

if(v未被通路&&以u為中介點可以使起點s到頂點v的最短距離d[v]更優){
	優化d[v];
	令v的前驅為u; 
} 
           

for(int v=0; v<n; v++) {
	if(vis[v]==false&&G[u][v]!=INF
	        &&d[u]+G[u][v]<d[v]){
	    d[v]=d[u]+G[u][v];
		pre[v]=u;//記錄v的前驅頂點是u  	
	}	
}
           

第二标尺

• ①給每條邊增加一個邊權（花費最小）
• ②給每個點增加一個點權（物資最大）
• ③直接問多少條最短路徑

①給每條邊增加一個邊權（花費最小）

for(int v=0; v<n; v++) {
	if(vis[v]==false&&G[u][v]!=INF){
		if(d[u]+G[u][v]<d[v]){
			d[v]=d[u]+G[u][v];
			c[v]=c[u]+cost[u][v];
		}else if(d[u]+G[u][v]==d[v]&&c[u]+cost[u][v]<c[v]){
			c[v]=c[u]+cost[u][v];
		}
	}	
}
           

②給每個點增加一個點權（物資最大）

for(int v=0; v<n; v++) {
	if(vis[v]==false&&G[u][v]!=INF){
		if(d[u]+G[u][v]<d[v]){
			d[v]=d[u]+G[u][v];
			w[v]=w[u]+weight[v];
		}else if(d[u]+G[u][v]==d[v]&&w[u]+weight[v]>w[v]){
			w[v]=w[u]+weight[v];
		}
	}	
}
           

③直接問多少條最短路徑

for(int v=0; v<n; v++) {
	if(vis[v]==false&&G[u][v]!=INF){
		if(d[u]+G[u][v]<d[v]){
			d[v]=d[u]+G[u][v];
			num[v]=num[u];
		}else if(d[u]+G[u][v]==d[v]&&w[u]+weight[v]>w[v]){
			num[v]+=num[u];
		}
	}	
}
           

題目連結：

1003 Emergency (25分)