最短路

BFS求最短路

BFS可用于求无权图的最短路，时间复杂度为\(O(m)\)，\(m\)为图上边的数量。

Floyd求最短路

Floyd用于求任意两点的最短路径，使用于任意图，无论有向无向，正权负权。时间复杂度为\(O(n^3)\)，\(n\)为节点数量。
设\(dp[i][j]\)是从\(i\)点到\(j\)的最短路径，最开始时每两个点之间的距离都为无穷大。
需要注意的是，用这种方法求得的\(dp[i][i]\)并不为0，所以需要特判。
当\(dp[i][i]\)为负数时，说明存在负环。

模板

for(int k = 1; k <= n; k++)
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);