Сложность времени объединения

Question

Мы имеем ориентированный граф G = (V, E), при котором каждое ребро (u, v) в E имеет относительное значение r (u, v) в R и 0 < = r (u , v) < = 1, который представляет надежность на канале связи от вершины u до вершины v.

Рассматривайте как r (u, v) вероятность того, что канал от u до v не сработает передача и что вероятности независимы. Я хочу написать эффективный алгоритм, который найдет наиболее надежный путь между двумя данными узлами.

Я попытался следующие:

DIJKSTRA(G,r,s,t) 
1. INITIALIZE-SINGLE-SOURCE(G,s) 
2. S=Ø 
3. Q=G.V 
4. while Q != Ø 
5.   u<-EXTRACT-MAX(Q) 
6.   if (u=t) return d[t] 
7.   S<-S U {u} 
8.   for each vertex v in G.Adj[u] 
9.    RELAX(u,v,r) 


INITIAL-SINGLE-SOURCE(G,s) 
1. for each vertex v in V.G 
2.  d[v]=-inf 
3.  pi[v]=NIL 
4. d[s]=1 



RELAX(u,v,r) 
1. if d[v]<d[u]*r(u,v) 
2 d[v]<-d[u]*r(u,v) 
3. pi[v]<-u 

, и я хотел, чтобы найти сложность алгоритма.

Сложность времени INITIALIZE-SINGLE-SOURCE (G, s) равна O (| V |). Временная сложность линии 4 равна O (1). Временная сложность линии 5 равна O (| V |). Сложность времени линии 7 равна O (log (| V |)). Сложность времени линии 8 равна O (1). Какая временная сложность команды S < -S U {u}? Строка 10 выполняется в сумме O (Σ_ {v \ in V} deg (v)) = O (E) раз, а временная сложность RELAX равна O (1).

Таким образом, временная сложность алгоритма равна временной сложности линий (3-9) + O (E). Какова временная сложность объединения?

Answer 1

Таким образом, временная сложность алгоритма равна времени сложность линий (3-9) + O (E). Какова временная сложность объединения ?

Нет, это не сложность объединения, объединение может быть выполнено довольно эффективно, если вы используете хеш-таблицу, например. Более того, поскольку вы используете S только для объединения, это кажется излишним.

Сложность алгоритма также в значительной степени зависит от EXTRACT-MAX(Q) функции (обычно это логарифмическая в размере Q, так logV на одну итерацию), и на RELAX(u,v,r) (который также обычно логарифмическая в размере Q, т.к. вам необходимо обновить записи в очереди приоритетов).

Как и ожидалось, это приводит нас к той же сложности оригинального алгоритма Дейкстры, который равен O(E+VlogV) или O(ElogV), в зависимости от реализации вашей очереди приоритетов.

Answer 2

Я думаю, что решение должно основываться на классическом алгоритме Дейкстры (сложность которого хорошо известна), как вы и предполагали, однако в вашем решении вы неправильно определяете проблему «кратчайшего пути».

Обратите внимание, что вероятность A и B равна p (A) * p (B) (если они независимы). Следовательно, вы должны найти путь, у которого умножение ребер максимизировано. В то время как алгоритм Дейкстры находит путь, который сумма ребер составляет сведено к минимуму.

Чтобы преодолеть эту проблему, вы должны определить вес ваших краев, как:

R * (и, v) = -log (R (и, v))

Вводя логарифм, вы преобразовать мультипликативную задачу в аддитив.