Алгоритм линейного времени для нахождения минимально-узкого пути - PullRequest
Новая
       49

Алгоритм линейного времени для нахождения минимально-узкого пути

0 голосов
/ 02 декабря 2018

Я беру онлайн-класс алгоритмов из Стэнфорда, и один из вопросов таков:

Определите узкое место пути как максимальную длину одного из его ребер.Путь с минимальным узким местом между двумя вершинами s и t - это путь с узким местом, не превышающим путь любого другого st-пути.Предположим теперь, что граф ненаправленный.Дайте алгоритм линейного времени (O (m)) для вычисления пути с минимальным узким местом между двумя заданными вершинами.

Решение этого с помощью модифицированного алгоритма Дейкстры выполняется в O (mlog (n)), чтоне соответствует требованию. Википедия утверждает, что

существует линейный алгоритм времени для нахождения самого широкого st-пути в неориентированном графе, который не использует максимальное связующее дерево.Основная идея алгоритма состоит в том, чтобы применить алгоритм нахождения линейного времени к среднему весу ребра в графе, а затем либо удалить все меньшие ребра, либо сжать все большие ребра в зависимости от того, существует ли путь или нет,и повторите в полученном меньшем графе.

Есть пара проблем.Алгоритм в основном ручной, и я не ищу самый широкий путь, а наоборот.

Эта статья содержит больше текста, чем Википедия, но она тоже не делаетвдаваться в кровавые подробности, особенно когда речь идет о сокращении краев.

Я записал следующий псевдокод: 

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*)

Несколько вещей, которые я не понимаю:

  1. Строка 6: какое имеет значение, удаляю ли я ребра с весом выше среднего или меньшим?
  2. Строка 20: есть 3 типа ребер, у которых обе вершины находятся за пределамисвязанный компонент, те, которые имеют как вершины в связанном компоненте, так и те, которые имеют одну вершину в связанном компоненте и одну вне.Первый тип сохраняет свой вес ребра, второй тип становится самоконтролем и должен быть удален (?).Каким должен быть вес ребра для третьего типа?

1 Ответ

0 голосов
/ 13 декабря 2018

ОП здесь.Подробное решение можно найти в моем блоге , но псевдокод выглядит следующим образом: 

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*)
...