最短路徑：Dijkstra、BellmanFord以及SPFA算法

最短路徑問題

• 1、Dijkstra算法
• • 簡介
  • （1）Dijkstra算法僞代碼
  • （2）C++ 鄰接表版代碼
  • （3）優化
  • （4）題型分析
• 2、Bellman Ford算法
• • 簡介
  • （1）Bellman算法僞代碼
  • （2）C++ 鄰接表版代碼
• 3、SPFA算法
• • 簡介
  • （1）SPFA算法僞代碼
  • （2）C++ 鄰接表版代碼

1、Dijkstra算法

簡介

Dijkstra算法用于計算單源最短路徑，即給定圖G(V,E)以及源點s，求s到其他頂點的最短路徑。

時間複雜度：

（1）Dijkstra算法僞代碼

dijkstra (G,s){
	初始化變量
	for 循環周遊n次{
			u為未通路過的節點中離s最近的頂點
			如果不存在u，那麼表示剩餘節點與s不連通，return;
			通路u
			for 周遊所有與u相連的頂點v{
				if 如果d[u] + dis<d[v]：
						證明經過u能夠使源點s到頂點v距離更短！
						更新d[v] = d[u] + dis
				}
	}
}
           

（2）C++ 鄰接表版代碼

//Dijstra算法
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

struct Node {
	int v, dis;
	Node(int _v, int _dis) {
		v = _v;
		dis = _dis;
	}
};


const int MAXV = 1000;
const int INF = 0x3fffffff;
int n, m, st, ed;
vector<Node> Adj[MAXV];
int d[MAXV];
bool vis[MAXV];//是否通路過

void dijkstra(int st) { //起點
	fill(d, d + MAXV, INF);
	d[st] = 0;
	memset(vis, false, sizeof vis);

	for (int i = 0; i < n; i++) {
		int u = -1; // 找出一個最短的地點攻占
		int min_distance = INF;
		for (int j = 0; j < n; j++) {
			if (vis[j] == false && d[j] < min_distance) {
				min_distance = d[j];
				u = j;
			}
		}
		if (u == -1) {
			//如果找不到小于INF的d[u]，說明剩下的節點與s不連通
			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;
			}
		}
	}
}


int main() {
	cin >> n >> m >> st >> ed; //n個頂點 m條邊
	int a, b, wt;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> wt;
		Adj[a].push_back(Node(b, wt));
		//Adj[b].push_back(Node(a, wt));  //無向圖時加上
	}

	dijkstra(st);
	for (int i = 0; i < n; i++) {
		cout << d[i] << endl;
	}
	return 0;
}
           

（3）優化

1）采用堆排序
	2）使用STL中的set
	3）使用STL中的prority queue （優先隊列）  時間複雜度降到O(VlogV+E）
           

（4）題型分析

在實際問題中，可能會存在有兩條及以上可達到的最短路徑，于是，題目會給出第二标尺（第一标尺是距離），要求在所有最短路徑中根據給定的第二标尺選擇最優的一條路徑。第二标尺通常情況是以下三種出題方式或者組合：

1）給每條邊增加一個 邊權 （比如說花費），比如說花費最小或者其他含義的邊權要求最大。
	2）給每個頂點增加一個 點權 （比如每個城市能夠收集的物資），要求在最短路徑下收集的物資最多。其他含義也可能求最小。
	3）直接問有多少條最短路徑。
           

解決：待更新 提示：增加一個pre數組

通路路徑？？？DFS

2、Bellman Ford算法

簡介

Dijkstra算法可以很好的解決無負權圖的最短路徑問題，但如果出現了負權邊Dijkstra算法就會失效。

為了更好的解決帶有負權邊的最短路徑問題，需要使用Bellman Ford算法。

環：根據環中的邊權之和的正負，可以将環分為零環、正環和負環。

如果圖中存在負環，且從源點可達，那麼會影響最短路徑的求解！

（1）Bellman算法僞代碼

時間複雜度：

采用鄰接表 – O(VE)

采用鄰接矩陣 – O(V^3)

for 循環V-1輪（因為搜尋樹的深度不能超過V-1，否則圖中有回路存在。）{
	循環每一條邊 u->v 
	for (int u =0;u<n;u++) { //對于頂點u
		for(int j=0;j<Adj[u].size();j++){//周遊與u連接配接的每一條邊
			int v = Adj[u][j].v;
			int dis = Adj[u][j].dis;
			if 如果d[u]+dis<d[v]://松弛操作
				更新d[v]=d[u]+dis;
		}
	}
}
           

（2）C++ 鄰接表版代碼

3、SPFA算法

簡介

雖然Bellman Ford算法很好的解決了負權值的問題，但由于它要周遊所有的邊，時間複雜度着實有點高了。認真思考後會發現，隻有當d[u]的值改變了，與之相連的v點 d[v]才有可能改變。根據該發現進行一個小的優化：建立一個隊列，每次取出隊首頂點u，對u出發的所有邊u->v進行松弛操作【即判斷d[u]+dis < d[v]，對d[v]進行優化。此時如果v不在隊列中，就将其加入隊列。因為d[v]改變了，與之相連的邊也可能改變。】直到隊列為空（說明圖中沒有後從源點可達的負權），或者是某個頂點的入隊次數超過V-1（說明圖中存在從源點可達的負環）。

（1）SPFA算法僞代碼

建立隊列q
源點入隊
當隊列不為空時：
	取出隊首元素u
	for 循環周遊u為起點的每一條邊v：
		if d[u]+dis<d[v]:
			更新d[v]
			if v 不在隊列中：	
				将其加入隊列
				num[v] += 1  //通路次數加一
				如果v的通路次數大于V-1：表示圖中存在源點可達的負權。
           

核心代碼：
queue<Node> q;
q.push(st);//源點入隊
num[st] += 1 //st通路次數加一
inq[st] = true;//st在隊列中
while q.empty()!=null:
	u = q.front();
	q.pop(); //取出隊首元素u
	inq[u] = false;

	for(int i=0;i<Adj[u].size();i++){
		int v = Adj[u][i].v;
		int dis = Adj[u][i].dis;
		if d[u]+dis<d[v]:
			d[v] = d[u]+dis;
			if inq[v]!=true:
				q.push(v);
				num[v] += 1
				if num[v] >= V:
					return false;
	}
           

（2）C++ 鄰接表版代碼