最短路問題彙總

author: jzh

date: 2021/9/20

site: https://akynazh.site

之前寫的幾個有點亂而且有些地方寫的不準确，這裡借着CSP比賽複習重新整理一下。

注意，這裡為了友善描述算法，是以都用了最易了解的鄰接矩陣來寫，比賽中為了追求效率，一般将鄰接矩陣改為鍊式前向星或者鄰接表。

迪傑斯特拉算法 O(V^2)

const int MAXN = 100;
const int INF = 0x3f3f3f3f;
// 有向無環圖 DAG
int V, E; 				// 頂點數和邊數
int graph[MAXN][MAXN];  // DAG鄰接矩陣，初始值為INF，不可達為INF，否則為cost值 
int d[MAXN]; 			// 從某點s出發到其它任意結點的最短路徑長度，初始值為INF 
int visited[MAXN]; 		// 某點是否通路過，通路過則為1否則為0

// 初始化圖 
void init() {
	memset(graph, 0x3f, sizeof(graph));
	cin >> V >> E;
	int from, to, cost;
	for (int i = 0 ; i < E; i++) {
		cin >> from >> to >> cost;
		graph[from][to] = cost;
	}
}
// 迪傑斯特拉算法求解最短路，針對點展開 
void Dijkstra(int s) {
	memset(d, 0x3f, sizeof(d));
	memset(visited, 0, sizeof(visited));
	visited[s] = 1;
	for(int i = 0; i < V; i++) d[i] = graph[s][i];
	d[s] = 0;
	int k, min_cost;
	// 無負邊時最多更新n-1(其他結點數)次 
	for(int i = 0; i < V - 1; i++){
		min_cost = INF;
		// 尋找最未被通路的且權值最小的路徑，需要優化的地方 
		for(int j = 0; j < V; j++){
			if(!visited[j] && d[j] < min_cost){
				k = j;
				min_cost = d[j];
			}
		}
		visited[k] = 1;
		// 利用找到的結點更新最短路徑
		for(int j = 0; j < V; j++){
			if(!visited[j] && min_cost + graph[k][j] < d[j]){
				d[j] = min_cost + graph[k][j];
			}
		}
	}
}

迪傑斯特拉算法的堆優化 O(ElogV) 不含負權就用它 ~

const int MAXN = 100;
const int INF = 0x3f3f3f3f;
// 有向無環圖 DAG
int V, E; 				// 頂點數和邊數
int graph[MAXN][MAXN];  // DAG鄰接矩陣，初始值為INF，不可達為INF，否則為cost值 
int d[MAXN]; 			// 從某點s出發到其它任意結點的最短路徑長度，初始值為INF 
int visited[MAXN]; 		// 某點是否通路過，通路過則為1否則為0

typedef pair<int, int> P; // first: 最短距離 second：通往的頂點編号 
priority_queue<P, vector<P>, greater<P> > que; // greater<T> 從小到大取出 

// 初始化圖 
void init() {
	memset(graph, 0x3f, sizeof(graph));
	cin >> V >> E;
	int from, to, cost;
	for (int i = 0 ; i < E; i++) {
		cin >> from >> to >> cost;
		graph[from][to] = cost;
	}
}
// 迪傑斯特拉算法堆優化求解最短路，針對點展開
void Dijkstra_optimise(int s) {
	memset(d, 0x3f, sizeof(d));
	memset(visited, 0, sizeof(visited));
	// for(int i = 0; i < V; i++) d[i] = graph[s][i];
	// 開始min_cost為0，若加上這一步，0 + graph[k][i]  == d[i] == graph[k][i]，導緻無法更新隊列 
	d[s] = 0;
	int k, min_cost;
	que.push(P(0, s));
	while (!que.empty()) {
		P p = que.top(); que.pop();
		// 通過堆優化直接獲得了目标 
		min_cost = p.first;
		k = p.second;
		// 若已經有更短的路徑則不更新 
		if (min_cost > d[k]) continue;
		visited[k] = 1;
		for (int i = 0; i < V; i++) {
			if (!visited[i] && min_cost + graph[k][i] < d[i]) {
				d[i] = graph[k][i] + min_cost;
				que.push(P(d[i], i));
			}
		} 
	} 
}

貝爾曼福德算法 O(VE)

using namespace std;
const int MAXN = 100;
const int MAXE = 100; 
const int INF = 0x3f3f3f3f;
// 有向無環圖 DAG
struct Edge {
	int from, to, cost;
};
int V, E; 				// 頂點數和邊數 
int d[MAXN]; 			// 從某點s出發到其它任意結點的最短路徑長度，初始值為INF 
Edge edge[MAXE];		// 邊集  

// 初始化圖 
void init() {
	cin >> V >> E;
	int from, to, cost;
	for (int i = 0 ; i < E; i++) 
		cin >> edge[i].from >> edge[i].to >> edge[i].cost;
}
// 貝爾曼福德算法求解最短路，針對邊展開 
void Bellman_Ford(int s)
{
	memset(d, 0x3f, sizeof(d));
	d[s] = 0;
	while (1) {
		int flag = 0;
		// DAG下最少更新E次
		for (int i = 0; i < E; i++) {
			Edge e = edge[i];
			if (d[e.from] != INF && d[e.to] > d[e.from] + e.cost) {
				d[e.to] = d[e.from] + e.cost;
				flag = 1;
			}
		}
		// 如果沒出現更新則退出
		if (!flag) break;
	} 
}

貝爾曼福德算法優化（SPFA + 優先隊列）含負邊就用它~

雖然大家都說SPFA已死，但其實是說笑罷了，含負權邊或者負環的題還真離不開這東西~

const int MAXN = 100;
const int INF = 0x3f3f3f3f;
// 有向無環圖 DAG
int V, E; 				// 頂點數和邊數
int graph[MAXN][MAXN];  // DAG鄰接矩陣，初始值為INF，不可達為INF，否則為cost值 
int d[MAXN]; 			// 從某點s出發到其它任意結點的最短路徑長度，初始值為INF 
int vis[MAXN]; 		 // 結點是否已入隊 
int push_count[MAXN]; // 結點入隊次數，若大于等于V，則證明存在負環 
priority_queue<int, vector<int>, greater<int> > que; // greater<T> 從小到大取出 

// 初始化圖 
void init() {
	memset(graph, 0x3f, sizeof(graph));
	cin >> V >> E;
	int from, to, cost;
	for (int i = 0 ; i < E; i++) {
		cin >> from >> to >> cost;
		graph[from][to] = cost;
	}
}
// SPFA算法求解最短路 
void SPFA(int s) {
	memset(d, 0x3f, sizeof(d));
	memset(vis, 0, sizeof(vis));
	memset(push_count, 0, sizeof(push_count));
	d[s] = 0;
	que.push(s);
	vis[s] = 1;
	push_count[s]++;
	while (!que.empty()) {
		int flag = 0; // 負環判斷 
		int v = que.top(); que.pop(); vis[v] = 0;
		for (int i = 0; i < V; i++) {
			if (d[v] + graph[v][i] < d[i]) {
				d[i] = d[v] + graph[v][i];
				if (!vis[i]) {
					que.push(i);
					vis[i] = 1;
					push_count[i]++;
					if (push_count[i] >= V) {
						flag = 1;
						break;
					}
				}
			}
		}
		if (flag) {
			cout << "有負環" << endl;
			break;
		} 
	} 
}

弗洛伊德算法 O(V^3) 多源問題可以考慮用它~

const int MAXN = 100;
const int INF = 0x3f3f3f3f;
// 有向無環圖 DAG
int V, E; 				// 頂點數和邊數
int graph[MAXN][MAXN];  // DAG鄰接矩陣，初始值為INF，不可達為INF，否則為cost值
int d[MAXN][MAXN];		// 從任意結點出發到其它任意結點的最短路徑長度，初始值為INF
 
// 初始化圖 
void init() {
	memset(graph, 0x3f, sizeof(graph));
	cin >> V >> E;
	int from, to, cost;
	for (int i = 0 ; i < E; i++) {
		cin >> from >> to >> cost;
		graph[from][to] = cost;
	}
}
// 弗洛伊德算法求解最短路
void Floyd()
{
	// 初始化矩陣d 
	memset(d, 0x3f, sizeof(d));
	for(int i = 0; i < V; i++)
		for(int j = 0; j < V; j++)
			d[i][j] = graph[i][j];
	for(int k = 0; k < V; k++){//以頂點k為中轉
		for(int i = 0; i < V; i++){//從頂點i到頂點j
			for(int j = 0; j < V; j++){
				if (d[i][j] > d[i][k] + d[k][j]) 
					d[i][j] = d[i][k] + d[k][j];
			}
		} 
	} 
}

附：

鍊式前向星

const int MAXN = 100;
struct Edge {
	int to; // 邊的終點 
	int next; // 與該邊同起點的下一條邊的編号 
	int w; // 邊的權值 
};
Edge edge[MAXN]; // 所有邊的集合
int head[MAXN]; // 所有起點的第一條邊的編号，初始化為-1 
int V, E;
// 建立圖 
void build() {
	int from, to, w, cnt = 0;
	for (int i = 0; i < E; i++) {
		cin >> from >> to >> w;
		edge[cnt].to = to;
		edge[cnt].w = w;
		edge[cnt].next = head[from]; 
        // 是以可将head初始化為-1，當next為-1時代表以該點為起點的邊通路結束 
		head[from] = cnt++;
	}
}
// 周遊整個圖 
void traverse() {
	for (int i = 0; i < V; i++) {
		for (int j = head[i]; j != -1; j = edge[j].next) {
			cout << " from " << i << " to " << edge[j].to << " weight: " << edge[j].w << endl;
		}
	}
}
// 周遊某個結點的鄰接點 
void traverse_v(int v) {
	for (int i = head[v]; i != -1; i = edge[i].next) {
		cout << " from " << v << " to " << edge[i].to << " weight: " << edge[i].w << endl; 
	}
}

over~

author: jzh

date: 2021/9/20

site: https://akynazh.site

最短路問題彙總最短路問題彙總

最短路問題彙總

迪傑斯特拉算法 O(V^2)

迪傑斯特拉算法的堆優化 O(ElogV) 不含負權就用它 ~

貝爾曼福德算法 O(VE)

貝爾曼福德算法優化（SPFA + 優先隊列）含負邊就用它~

弗洛伊德算法 O(V^3) 多源問題可以考慮用它~

鍊式前向星

繼續閱讀

Codeforces 1417 D. Make Them Equal(思維+構造)

查找算法之二分查找查找算法之二分查找

查找算法學習之二分查找（Python版本）——BinarySearch

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希