代码之家 › 专栏 › 技术社区 › Abhijit Sarkar

寻找最小瓶颈路径的线性时间算法

minimum-spanning-tree graph-algorithm graph-theory algorithm

Abhijit Sarkar · 技术社区 · 6 年前

我正在斯坦福大学学习一门在线算法课程,其中一个问题如下:

将路径瓶颈定义为其中一条路径的最大长度现在假设图是无向的。给出一个线性时间(O(m)) 计算两个给定节点之间最小瓶颈路径的算法

用一个改进的Dijkstra算法来解决这个问题,该算法运行在不满足要求的O(mlog(n))中。 Wikipedia 声称有

存在一个线性时间算法,用于在一个数据集中查找最宽的s-t路径无向图,不使用最大生成树。这个该算法的主要思想是应用线性时间路径搜索路径是否存在,并在结果中递归

有两个问题。算法主要是挥手,我不是在寻找最宽的路径,而是相反。

This 纸上的文字比维基百科的多,但它也不涉及血淋淋的细节,特别是当涉及到收缩边缘时。

1: MBP(G, s, t)
2:  if |E| == 1
3:    return the only edge
4:  else
5:    x = median of all edge weights
6:    E' = E - (v, w) where weight(v, w) < x
7:    construct G'(V, E')
8:    exists = is there a path from s to t in G'

9:    if (exists == FALSE)
10:      compute all the connected components Cáµ¢ of G'
11:      reinsert the edges deleted into G'

12:      G* = G'
13:      for each Cáµ¢
14:        G* = SHRINK(G*, Cáµ¢)

15:  return MBP(G', s, t)

16: SHRINK(G, C)
17:  leader = leader vertex of C
18:  V* = {V(G) - C} âª {leader}

19:  E* = {}
20:  for each edge (v, w) â E(G)
21:    if v, w â V*
22:      E* = E* âª {(v, w, weight(v, w))}
23:    else if v â C, w â V*
24:      E* = E* âª {(leader, w, max(weight(v, w)))}

25:  return G*(V*, E*)

有几件事我不明白:

第6行:删除权重高于中间值或低于中间值的边有什么关系?
第20行:有3种类型的边,即在连接的组件外部有两个顶点的边,在连接的组件中有两个顶点的边,在连接的组件中有一个顶点的边,以及在连接的组件中有一个顶点的边。第一种类型保留其边权重,第二种类型成为自循环,应删除(?)。第三种类型的边缘权重应该是多少?

1 回复 | 直到 6 年前

Abhijit Sarkar 6 年前

在这里。有关详细解决方案,请参阅 my blog

1: CRITICAL-EDGE(G, s, t)
2:   if |E(G)| == 1
3:     return the only edge
4:   else
5:     x = median of all edge weights
6:     X = E - (v, w) s.t. weight(v, w) > x
7:     G' = G(V, X)
8:     exists = is there a path from s to t in G'

9:     if (exists == FALSE)
10:      C = {Câ, Câ, ..., Câ} s.t. Cáµ¢ is a connected component of G
11:      G' = G(V, E - X)

12:      for i = 1 to |C|
13:        G' = SHRINK(G', C, i)
14:    else if X == E // no edges were deleted
15:      X = {(v, w)} s.t. weight(v, w) = x
16:      G' = G(V, X)

17:  return CRITICAL-EDGE(G', s, t)

18: SHRINK(G, C, i)
19:   leaderáµ¢ = leader vertex of C[i]
20:   V* = {V(G) - C[i]} âª {leaderáµ¢}

21:   E* = {}
22:   for each (v, w) â E(G)
23:     if v â C[i], w â C[j]
24:       E* = E* âª {(leaderáµ¢, leaderâ±¼, min(weight(u, w)))} â u â C[i]
25:     else if v, w â C[i]
          E * = E* âª {(v, w, weight(v, w))}

26:   return G*(V*, E*)