# 单源最短路问题

# 基本概念

初始化过程定义顶点的最短距离 d[v] , 边权值矩阵 w[u][v] 和前驱数组 pi[v] .

initializeSingleSource

	void initializeSingleSource(Graph G, int s) {
	for (int v:G.vertices) {
	d[v] = INT_MAX;
	pi[v] = NULL;
	}
	d[s] = 0; // source
	}

可以解决存在负权边情况下的单源最短路问题。

算法的核心是松弛 (relax) 技术。

relax

这样，Bellman-Ford 算法可以描述为下述代码：

BellmanFord

	bool BellmanFord(Graph G, int s) {
	// initialize
	initializeSingleSource(G, s);

	for (auto v:G.vertices) {
	for (auto e:G.edges) {
	relax(e.from, e.to);
	}
	}

	for (auto e:G.edges) {
	int u = e.from;
	int v = e.to;
	if (d[v] > d[u] + w[u][v]) return false;
	}

	return true;
	}

可以看出，Bellman-Ford 算法的复杂度是 $O(nm)$ 的。

需要注意的是，以 $s$ 点为源点跑 Bellman–Ford 算法时，如果没有给出存在负环的结果，只能说明从 $s$ 点出发不能抵达一个负环，而不能说明图上不存在负环。

因此如果需要判断整个图上是否存在负环，最严谨的做法是建立一个超级源点，向图上每个节点连一条权值为 $0$ 的边，然后以超级源点为起点执行 Bellman–Ford 算法。

SPFA 是队列优化的 Bellman-Ford 算法。最差复杂度仍为 $O(nm)$ , 伪代码如下：

SPFA

是一种求解非负权图上单源最短路径的算法。

Dijkstra

这是暴力的写法，复杂度是 $O(n^2 + m) = O(n^2)$ 的。

如果对于稀疏图，采用二叉堆维护边的插入情况，那么复杂度可以优化到 $O((n+m) \log n)$ . 对于稀疏图 ( $m < n^2/\log n$ ), 这是一个不错的优化。

如果采用斐波那契堆优化，那么复杂度可以降低到 $O(n \log n+m)$ .

只有三层 for , 简单快捷 *。复杂度 $O(n^3)$ .

Floyd_Warshall

是否存在负权，只需要观察 f[n][i][j] 中的对角线元素 ( i==j ) 中是否存在负元即可。

复杂度 $O(n^2 \log n + nm)$ .

步骤如下：