Сложность многоступенчатого графа - PullRequest
Новая
       28

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

0 голосов
/ 22 марта 2012

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

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

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 работает для общего числа вершин, и внутренняя линия должна выбрать ближний край.

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

1 Ответ

0 голосов
/ 22 марта 2012

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

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

...