圖論總結

最短路

注：表中的 Dijkstra 算法在計算復雜度時均用 priority_queue 實現。

Floyd

適用范圍：無論有向圖還是無向圖，無論是否有負邊。（正常運行）不能有負環。

定義數組f[k][x][y]，表示只允許經過1-k的節點，x到y的最短路徑長度。（x,y不一定要在1-k中）
本質是dp。第一維可壓。
初始化：邊權，或0（x=y），或inf（不連接）。

int e[maxn][maxn], f[maxn][maxn];

void floyd()
{
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
		{
			f[i][j] = (e[i][j] == -1 ? inf : e[i][j]);
			if (i == j)
				f[i][j] = 0;
		}
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}

Bellman–Ford

適用范圍：允許有負邊，可以判斷負環。
松弛操作：dis(v) = min(dis(v), dis(u) + w(u, v)) 。

關于負環:
若存在最短路（沒有負環），由于每一次松弛會使得最短路邊數至少 +1，而最短路的邊數最多為 n-1，因此整個算法最多執行 n-1 輪松弛操作。若第n輪還能繼續，則存在負環。
需要注意，從S出發能跑出最短路，不代表一定沒有負環（如有向圖，或不屬于同一個分量的情況）。正確做法是建立一個超級原點S'，從它向每個點連一條邊權為0的邊，然后從這個點開始跑。（不過如果只是找S的最短路也無所謂了）

只有上一次被松弛的結點，所連接的邊，才有可能引起下一次的松弛操作。所以有了SPFA，即隊列優化。
SPFA會被卡，所以一般情況用Dijkstra。

bool SPFA()//返回true代表有最短路，否則有負環
{
	memset(dis,0x3f,sizeof(dis));//由于memset的妙妙特性，dis會變成0x3f3f3f3f
	queue<int> qu;
	dis[s]=0,inque[s]=1;
	qu.push(s);
	while (!qu.empty())
	{
		int u=qu.front();
		qu.pop();inque[u]=0;
		for(edge ed:e[u])//相當于for(int i=0;i<e[u].size();i++)edge ed=e[u][i]
		{
			int v=ed.v,w=ed.w;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				cnt[v]=cnt[u]+1;
				if(cnt[v]>=n)
					return false;//大于等于n，有負環
				if(!inque[v]) 
					qu.push(v), inque[v]=1;
			}
		}
	}
	return true;
}

Dijkstra

適用范圍：非負權圖（可以有0）
思路：將結點分成兩個集合：已確定最短路長度的點集（記為 S 集合）的和未確定最短路長度的點集（記為 T 集合）。一開始所有的點都屬于 T 集合。每次從T中選取一個最短路長度最小的結點，移到 S 集合中，并進行松弛操作。
本質為貪心。

struct edge{
	int u,v,w;
};
struct node{
	int u,dis;
	bool operator > (const node& b) const {return dis>b.dis;};//用于greater；const不能少
};
vector<edge> e[maxn];
int dis[maxn], vis[maxn];
priority_queue<node, vector<node>, greater<node>> pq;

void dijkstra()
{
	memset(dis, 0x3f, (n + 1) * sizeof(int));
	memset(vis, 0, (n + 1) * sizeof(int));
	dis[s]=0;
	pq.push({s,0});
	while (!pq.empty())
	{
		int u=pq.top().u;
		pq.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(edge ed:e[u])
		{
			int v=ed.v,w=ed.w;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				pq.push({v,dis[v]});
			}
		}
	}
}

Johnson

適用范圍：全源最短路，可以有負邊，不能有負環。

跑n遍Dijkstra實現全源最短路的復雜度是\(O(nm\log m)\)，在稀疏圖上比Floyed更優。但是Dijkstra不能解決負邊。因此需要將值全部調整為正的。

新建虛擬節點0，從0向所有節點連一條權為0的邊。（注：即使是無向圖，也只用添加單向的邊）接下來從0開始求最短路，記為h[i]。如果一條邊從u到v，權為w，則新的權值為為 \(w+h_u-h_v\)。然后從每個節點跑一次Dijkstra。

模板：洛谷P5905

//公共部分
const int maxn = 3e3+10;
int n,m;

struct edge{
	int u,v,w;
};
vector<edge> e[maxn];

//spfa變量區
int h[maxn],cnt[maxn],inque[maxn];
const int inf = 1e9;

bool SPFA(int s)//返回true代表有最短路，否則有負環
{
	for(int i=1;i<=n;i++)
		h[i]=inf;
	queue<int> qu;
	h[s]=0,inque[s]=1;
	qu.push(s);
	while (!qu.empty())
	{
		int u=qu.front();
		qu.pop();inque[u]=0;
		for(edge ed:e[u])//相當于for(int i=0;i<e[u].size();i++)edge ed=e[u][i]
		{
			int v=ed.v,w=ed.w;
			if(h[v]>h[u]+w)
			{
				h[v]=h[u]+w;
				cnt[v]=cnt[u]+1;
				if(cnt[v]>=n+1)//注意在Johnson中是n+1,因為有0號原點
					return false;//大于等于n+1，有負環
				if(!inque[v]) 
					qu.push(v), inque[v]=1;
			}
		}
	}
	return true;
}

//dijkstra變量區
struct node{
	int u,dis;
	bool operator > (const node& b) const {return dis>b.dis;};//用于greater；const都不能少
};
int dis[maxn], vis[maxn];
priority_queue<node, vector<node>, greater<node>> pq;

void dijkstra(int s)
{
	for(int i=1;i<=n;i++)
		dis[i]=inf;
	memset(vis, 0, (n + 1) * sizeof(int));
	dis[s]=0;
	pq.push({s,0});
	while (!pq.empty())
	{
		int u=pq.top().u;
		pq.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(edge ed:e[u])
		{
			int v=ed.v,w=ed.w;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				pq.push({v,dis[v]});
			}
		}
	}
}

void johnson()
{
	for(int i=1;i<=n;i++)
		e[0].push_back({0,i,0});
	bool y=SPFA(0);
	if(!y)
	{
		cout<<-1<<endl;
		return;
	}
	for(int i=1;i<=n;i++)
		for(edge& ed:e[i])
			ed.w=ed.w+h[ed.u]-h[ed.v];//重新賦值
	for(int i=1;i<=n;i++)
	{
		dijkstra(i);
		int ans=0;
		for(int j=1;j<=n;j++)//本題要求是這么處理，其他題看情況
		{
			if(dis[j]==inf)
				ans+=j*inf;//這里需要注意，最后不要用dis[j]+h[j]-h[i]對inf算
			else
				ans+=j*(dis[j]+h[j]-h[i]);//別忘記了
		}
		cout<<ans<<endl;
	}
}