dijkstra算法的優化

題目

題目來源

P4779 【模闆】單源最短路徑（标準版）

題目描述

給定一個 nn 個點，mm 條有向邊的帶非負權圖，請你計算從 ss 出發，到每個點的距離。

資料保證你能從 ss 出發到任意點。

輸入格式

第一行包含四個正整數 n,m,s,tn,m,s,t，分别表示點的個數、有向邊的個數、源點序号、彙點序号。

接下來M行每行包含三個正整數ui, vi, wi, 表示第 i 條有向邊從 ui 除法，到達 vi, 邊權為 wi（即該邊最大流量為wi）。

輸出格式

一行，包含一個正整數，即為該網絡的最大流。

輸入樣例

4 5 4 3

4 2 30

4 3 20

2 3 20

2 1 30

1 3 40

輸出樣例

50

資料範圍

1 <= n <= 1e5;

1 <= m <= 2e5;

s = 1;

1 <= ui, vi <= n;

1 <= wi <= 1e9;

做法詳解

PS：這道題目是個經典的最短路，我們在這裡使用dijkstra算法來解決。因為在于對該算法的優化，是以不講解 dijkstra 算法的原理和實作。

最普通的dijkstra：(鍊式前向星存圖)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
using namespace std;
const int inf = 0x3f3f3f3f;

int m, n, s, cnt;
int head[1005], dist[1005], vis[1005];
struct {
	int to;
	int w;
	int next;
}edge[1005];

//存圖
void add(int u, int v, int w)
{
	edge[cnt].to = v;
	edge[cnt].w = w;
	edge[cnt].next = head[u];
	head[u] = cnt++;
}

//dijkstra算法
void dijkstra()
{
	for (int i = 1; i <= n; i++)
		dist[i] = inf;
	vis[s] = 1;
	dist[s] = 0;
	for (int i = head[s]; i != -1; i = edge[i].next)
		dist[edge[i].to] = min(dist[edge[i].to], edge[i].w);
	for (int i = 1; i <= n; i++)
	{
		int mid = inf;
		int idx;
		for (int j = 1; j <= n; j++)
		{
			if (!vis[j] && dist[j] < mid)
			{
				mid = dist[j];
				idx = j;
			}
		}
		for (int j = head[idx]; j != -1; j = edge[j].next)
		{
			dist[edge[j].to] = min(dist[edge[j].to], edge[j].w + dist[idx]);
		}
	}
}

int main()
{
	cin >> n >> m >> s;
	memset(head, -1, sizeof(head));
	for (int i = 0; i < m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w);
	}
	dijkstra();
	for (int i = 1; i <= n; i++)
		cout << dist[i] << ' ';
	return 0;
}
           

寫完了後我們滿心歡喜的交一發，會發現所有的測試資料都是 tle，搞人心态。dijkstra 算法的時間複雜度是O(n2)，是以對于 n 最大是1e5的資料肯定是會逾時的，是以我們需要優化。

優化目标

我們知道 dijkstra 算法的實作中，每一次會找到起點到所有邊的最小距離的點，然後用該點來松弛其他的點，進而達到起點到任意一點都是最短的距離。那麼我們能否把找最小距離點這一個步驟優化一下呢？當然是可以的。對于最初的周遊的 n 的複雜度，找最小值我們可以使用 logn 複雜度的線段樹或者優先隊列來優化代碼。

進行優化後，整體的複雜度會從O(n2)變為O( (m+n)logn )，大大降低了複雜度，即可AC本題。

線段樹優化

因為我們找到最小值後，需要這個最小值的節點來進行松弛，是以線段樹需要維護最小值 mi, 對應的節點 idx 兩個資料

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define ln (node << 1)//左兒子
#define rn (node << 1 | 1)//右兒子
#define mid ((l + r) >> 1)//中間值
//位運算加速

const int INF = 0x3f3f3f3f;
const int N = 1e5 + 5;
const int M = 2e5 + 5;

int n, m, s, cnt;
int head[N], dist[N], vis[N];
struct {
	int to;
	int w;
	int next;
}edge[M];//鍊式前向星

struct {
	int idx, mi;
}tree[N << 2];//線段樹

//更新節點
void update(int node)
{
	if (tree[ln].mi < tree[rn].mi)
	{
		tree[node].mi = tree[ln].mi;
		tree[node].idx = tree[ln].idx;
	}//左兒子小，父節點儲存左兒子的距離和節點
	else
	{
		tree[node].mi = tree[rn].mi;
		tree[node].idx = tree[rn].idx;
	}//右兒子小
}

//正常建樹操作
void build(int l, int r, int node)
{
	if (l == r)
	{
		tree[node].mi = dist[l];
		tree[node].idx = l;
		return;
	}
	else
	{
		build(l, mid, ln);
		build(mid + 1, r, rn);
		update(node);
	}
}

//鍊式前向星加邊
void add(int u, int v, int w)
{
	edge[cnt].w = w;
	edge[cnt].to = v;
	edge[cnt].next = head[u];
	head[u] = cnt++;
}

//用完一個節點後，把這個節點維護的最小值指派為無窮大
void change(int node, int l, int r, int x, int y, int z)
{
	if (l >= x && r <= y)
	{
		tree[node].mi = z;
		return;
	}
	if (r<x || l>y)
		return;
	change(ln, l, mid, x, y, z);
	change(rn, mid + 1, r, x, y, z);
	update(node);
}

void dijkstra()
{
	for(int i = 0; i < n - 1; i++)
	{
		int minn = tree[1].mi;//線段樹下标為1就是根節點，維護整個區間的資訊
		int idx = tree[1].idx;
		change(1, 1, n, idx, idx, 2147483647);//取出最小值後，把這個節點指派無窮大
		vis[idx] = 1;
		for (int j = head[idx]; j != -1; j = edge[j].next)
		{
			if (dist[edge[j].to] > dist[idx] + edge[j].w)
			{
				dist[edge[j].to] = dist[idx] + edge[j].w;//dijkstra正常操作
				if(!vis[edge[j].to])
					change(1, 1, n, edge[j].to, edge[j].to, dist[edge[j].to]);//如果進行了松弛操作，那麼也需要更新這個節點的距離資訊
			}
		}
	}
}

int main()
{
	cin >> n >> m >> s;
	memset(head, -1, sizeof(head));
	memset(dist, INF, sizeof(dist));
	dist[s] = 0;
	build(1, n, 1);
	while (m--)
	{	
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w);
	}
	dijkstra();
	for (int i = 1; i <= n; i++)
		cout << dist[i] << ' ';
	return 0;
}
           

優先隊列優化

相比于線段樹，代碼量更小，通俗易懂。

如果對于優先隊列有不懂的，自行學習。

#include <algorithm>
#include <queue>
#include <iostream>
#include <cstring>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const int N = 2e5 + 5;
const int INF = 1e9;

int n, m, s, head[N], cnt, dis[N], vis[N];

//鍊式前向星存邊
struct Edge {
	int to, w, next;
}e[N];

//加邊
void add(int u, int v, int w)
{
	e[cnt].w = w;
	e[cnt].to = v;
	e[cnt].next = head[u];
	head[u] = cnt++;
}

void dij()
{
	priority_queue<P, vector<P>, greater<P> > que;//建立一個維護最小值的優先隊列
	//這裡不能弄反的就是pair的first值，因為優先隊列會先對p.first進行排序，如果一樣才根據p.second排序
	for (int i = 1; i <= n; i++)
		dis[i] = INF;
	dis[s] = 0;
	que.push(P{ 0, s });//把起點放入隊列，距離是第一個值，對應節點是第二個值
	while (!que.empty())
	{
		P p = que.top();//堆頂就是目前的距離起點最小值節點
		que.pop();
		int mi = p.first;
		int idx = p.second;
		if (vis[idx])
			continue;//如果該點已經被當作中間點，則直接進行下一輪
		vis[idx] = 1;
		for (int i = head[idx]; i != -1; i = e[i].next)
		{
			int v = e[i].to;
			int w = e[i].w;
			if (dis[v] > dis[idx] + w)
			{
				dis[v] = dis[idx] + w;
				if (!vis[v])
					que.push(P{dis[v], v});//被更新的點就加入隊列
			}
		}
	}
}

int main()
{
	cin >> n >> m >> s;
	memset(head, -1, sizeof(head));
	while (m--)
	{
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w);
	}
	dij();
	for (int i = 1; i <= n; i++)
		cout << dis[i] << ' ';
	return 0;
}