最小生成树(MST)问题
- 对象: 该问题总是针对连通无向图G = (V, E);
- 总体算法
- 这个算法理出大概的思路, 真正实现还分为点和边两种方式;
Generic-MST(G, w) //w是权重函数
A = ∅
while A does not form a spanning tree
find an edge(u,v) that is safe for A
A = A∪(u,v)
return A //the minimum spanning tree
- 总体性质: A是图G=(V, E)中E的在SpanningTree中的边的集合, 如果(u,v)是横跨切割(S, V-S)的轻量级边, 其中S是SpanningTree的意思, 那么边(u, v)对于集合A是安全的;
证明: (分类讨论)
--如果(u, v)在STree中, 那么命题得证(安全边才能被收入A中);
--如果(u,v)不在STree中, 因为u,v两个点都在STree中, 那么必然在A中已经通过某种路径相连, 这条路径加上(u,v)边会形成一个环路, 且此时至少有两条边跨越了切割, 一个是(u, v), 另外一个不妨写作(x, y). 若断掉(x,y)留下(u, v) 则此时T'.w = T.w + w(u, v) - w(x, y), 因为(u, v)是轻量级边, 所以T'.w <= T.w, 所以说(u,v)边是安全的;
prim算法
- 思路: 并点, 不断找新生成树的切割面的最短边, 是典型的贪心算法;
MST-Prim(G, w, r) //Graph, weight, root
for each u ∈ G.V
u.key = ∞
u.parent = null
r.key = 0
Q = G.V //initiate a priority queue, 初始化结束
while Q != ∅:
u = Extract-Min(Q) //依据的是u.key是Q中最小的;
for each v∈G.Adj[u]:
if v∈Q and w(u, v)<v.key:
v.parent = u
v.key = w(u, v)
Note: 获取MST的时候, 只要让每个非root的结点u输出(u, u.parent)边;
- 时间复杂度分析:
(1) 使用二维数组W存储weight, 一维数组V存储结点: 初始化操作Θ(V);Extra-Min操作V次, 每次耗时Θ(V), 所以这个环节是Θ(V^2); 对边的操作, 总共有E条边, 每次耗时都是Θ(1), 因此这个环节Θ(E); 总体耗时因此是Θ(V^2+E);
(2) 使用二叉堆构建最小优先队列, Extract-Min耗时总共O(VlgV), 对边的操作需要做E次Decrease-Key, 耗时总共O(ElgV); 总体耗时因此为O((V+E)lgV), 因为E>=V-1总是成立, 因此可以写作O(ElgV);
(3) 使用斐波那契堆实现最小优先队列Q的话, Extract-Min时间仍是lgV, 但是Decrease-Key下降到O(1), 因此总体上时间是O(VlgV+E), 小于O(ElgV).
Kruskal算法
- 思路: 并边, 不断找整个图中最短边, 只要不构成环, 即相互不连通, 就并入, 也是贪心算法;.
MST-Kruskal(G, w)
A = ∅
for each u ∈ G.V
Make-Set(u)
sort the edges of G.E as ascending order by weight w //到此初始化完成
for edge(u, v) of the sorted edge sequence
if Find-Set(u) != Find-Set(v):
A = A ∪ { (u,v) } //add edge to A;
Union(u, v) //combine two trees
return A //A is the tree;
- 时间复杂度分析: 排序消耗了O(ElgE), 在改进过的并查集中, Find-Set总共做了E次, 消耗O(E), 而Union总共做了V次, 消耗O(Vα(V)), 其中α(V)<=4, 可以看作O(lgV), 因此Union消耗了O(VlgV), 因此并边循环总共消耗O(E+VlgV), 显然dominator是排序操作, 因此总体来说 T = O(ElgE).
网路最短路径问题
- 对象: 带权重的有向图G = (V, E); 注意和最小生成树的主要区别在于这是有向图!!!
共用方法
- 初始化
Initialize-Single-Source(G, s)
for each vertex v ∈ G.V:
v.d = ∞
v.parent = null
s.d = 0
- 松弛操作
Relax(u, v, w)
if v.d > u.d+w(u,v):
v.d = u.d+w(u,v)
v.parent = u
松弛定理: 对v点, 如果从s点到vi确实存在一条最短路径, 那么只要(s, v1), (v1, v2), ... (vi-1, vi)都被依次执行了relax操作, 那么vi.d = δ(s, vi). 该性质的成立与其他穿插在该序列中间的松弛操作无关.
- 也就是说, 接下去的三个算法, 我们都要检查松弛定理是否能运用, 只要能运用, 算法是正确的;
1. 一般情况下的单源最短路径问题
- 条件宽松: 允许出现负权重的环路;
Bellman-Ford(G, w, s) {
Initialize-Single-Source(G, s)
for i = 1~|V|-1:
for each edge(u, v) ∈ G.E:
relax(u, v)
for each edge(u, v) ∈ G.E:
if v.d >u.d+w(u, v): //只要任何一条边仍能继续松弛, 那么说明有负权重的环路存在;
return FALSE
return TRUE
}
正确性:
(1) 对某个点vi来说, 从s如果有一条最短路径, 那么在算法的第一个for循环, 到第i次循环, 该最短路径上的边(s, v1), (v1, v2)...(vi-1,vi)都将被松弛, 因此该算法能满足松弛定理, 使得vi.d = δ(s, vi);
(2) 最短路径上界定理: 对所有的最短路径来说, 最多只能有V-1条边, 否则将形成一个环. 因此Bellman-Ford算法只需要V-1轮全体relax就能cover到即使是最长的那条最短路径.
- 时间复杂度分析: 主要时间消耗在V-1次轮的全体relax, 一共消耗了O(VE);
2. 有向无环图中的单源最短路径问题
- 条件收紧: 允许使用负权重的边;
- 借助拓扑序
DAG-Shortest-Path(G, w, s) {
topologically sort the vertices of G
Initialize-Single-Source(G, s)
for each vertex u taken by the sorted order:
for each v of G.adj[u]:
Relax(u, v, w)
}
正确性: 因为是按照拓扑序对所有的边进行松弛, 因此最短路径上的边(s, v1), (v1, v2)...(vi-1,vi)的边, 都会被依次松弛, 尽管中间可能穿插其他的松弛, 最后必然能实现vi.d = δ(s, vi)
迪杰斯特拉算法
- 条件进一步收紧: 只允许非负权重的边;
- 思路:
对每个节点赋值∞, 每次都并一个距离最小的结点, 同时更新该结点的adj结点, 不断迭代;
Dijkstra(G, w, s) {
Initialize-Single-Source(G, s)
S = ∅
Q = G.V //初始化完成
while Q != ∅:
u = Extract-Min(Q)
S = S∪{u} //add u to S;
for each vertex v of G.adj[u]:
Relax(u, v, w)
}
正确性: Dij算法每次收入的点是当前Q中(尚未被染色的)满足d最小的点u, u.d此时已经满足被所有S中能到v的点给更新了. 那么为什么不担心之后加入S的点可能还会再减小v.d呢? 这是因为之后再加S的点, 必须经过之前的S的点, 这些后加点的v.d只可能在已有能连到它的点的基础上递增, 因为Dij算法要求图中没有负权重边.
- 时间复杂度分析:
(1) 使用二维数组W存储weight, 一维数组V存储结点: 初始化操作Θ(V);Extra-Min操作V次, 每次耗时Θ(V), 所以这个环节是Θ(V^2); 对边的操作, 总共有E条边, 每次耗时都是Θ(1), 因此这个环节Θ(E); 总体耗时因此是Θ(V^2+E); (注意到V-1<=E<=V^2, 因此可以写成Θ(V^2)).
(2) 使用二叉堆构建最小优先队列, Extract-Min耗时总共O(VlgV), 对边的操作需要做E次Decrease-Key, 耗时总共O(ElgV); 总体耗时因此为O((V+E)lgV), 因为E>=V-1总是成立, 因此可以写作O(ElgV);
(3) 使用斐波那契堆实现最小优先队列Q的话, Extract-Min时间仍是lgV, 但是Decrease-Key下降到O(1), 因此总体上时间是O(VlgV+E), 小于O(ElgV).
实际实现Dij算法的C++代码，对应743. 网络延迟时间 - 力扣（LeetCode）
class Solution {
struct Edge {
int to;
int weight;
Edge(int to, int weight) : to(to), weight(weight) {}
};
// only used for pq
struct Vertex {
int index;
int d;
Vertex(int index, int d) : index(index), d(d) {}
};
struct Compare {
bool operator()(const Vertex& a, const Vertex& b) {
return a.d > b.d;
}
};
public:
vector<int> Dijkstra(vector<vector<Edge>>& G, int n, int src)
{
vector<int> distanceTo(n + 1, INT_MAX);
priority_queue<Vertex, vector<Vertex>, Compare> minPQ;
minPQ.push(Vertex(src, 0)); // 这里和伪代码不一样，实际实现的时候PQ无法动态更新元素的key，需要只给一个src节点
while (minPQ.size())
{
Vertex u = minPQ.top();
// cout << "u:" << u.index << "," << u.d << endl;
minPQ.pop();
if (distanceTo[u.index] < INT_MAX) continue; // done this vertex before
distanceTo[u.index] = u.d;
for (Edge e : G[u.index])
{
int vIndex = e.to;
// cout << "distanceTo[v.index]:"<< vIndex << ",d:"<< distanceTo[vIndex] << endl;
if (distanceTo[vIndex] > distanceTo[u.index] + e.weight)
{
minPQ.push(Vertex(vIndex, distanceTo[u.index] + e.weight)); // 实际实现的时候relax操作表示为插入minPQ, 而不是更新节点值
}
}
}
return distanceTo;
}
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
vector<vector<Edge>> G(n + 1); // 0 not used, index = 1 ~ n
for (int i = 0; i < times.size(); i++)
{
G[times[i][0]].emplace_back(times[i][1], times[i][2]);
}
auto distanceTo = Dijkstra(G, n, k);
int maxTime = -1;
for (int i = 1; i <= n; i++)
{
maxTime = max(maxTime, distanceTo[i]);
}
// if some point is not reacheable
if (maxTime == INT_MAX) maxTime = -1;
return maxTime;
}
};
