Сложность многоступенчатого графа

Я просматривал книгу «Основы компьютерных алгоритмов» для многоэтапной задачи с графом.

В нем говорится:

Algorithm Graph(G,k,n,p)
{
cost[n]=0;
for j=n-1 to 1 step -1 do
{
Let r be a vertex such that<j,r> is an edge of G and c[j,r]+cost[r] is minimum
cost[j]=c[j,r]+cost[r]
}
}

Автор говорит, что сложность O(|V| + |E|). Где |V| — количество вершин и |E| это количество ребер.

Я знаю, что цикл for выполняется для общего количества вершин, а внутренняя линия должна выбирать ближнее ребро.

Я не мог понять логику позади


algorithm time-complexity complexity-theory asymptotic-complexity
person user567879    schedule 22.03.2012    source источник
comment
Если каждая вершина хранит список инцидентных ей ребер, то каждое ребро проверяется один раз.   -  person n. 1.8e9-where's-my-share m.    schedule 22.03.2012
comment
Может ли кто-нибудь сказать мне, что делает step -1 в указанном выше алгоритме ??.... Я следую той же книге, что и вопрос... и застрял там....   -  person Arnav Das    schedule 26.03.2018

Ответы (1)


arrow_upward
0
arrow_downward

Чтобы лучше понять, посмотрите на алгоритм Дейсктры на произвольном орграфе, каждое ребро также рассматривается только один раз. Время выполнения равно O(|E| + |V lg V|).

Поскольку многоэтапный граф разбит на наборы, вы можете найти кратчайший путь по набору, потому что вы знаете, что вершины в наборе X до целевого узла должны быть посещены до набора X-1. Вы также знаете, что вершины в одном наборе не имеют ребер между собой. Короче говоря, вы знаете, в каком порядке их обрабатывать, и вам не нужно каждый раз рассматривать все возможные вершины, как в Dijsktra.

person dfb    schedule 22.03.2012
comment
Это похоже на проблему преобразования DAG в топологический порядок и последующего поиска кратчайшего пути с одним источником? - person Surbhi Jain; 09.07.2019