Граф имеет n вершин. Сколько изменений пометок сделает алгоритм Дейкстры в худшем случае?

задан 9 Янв '15 14:40

10|600 символов нужно символов осталось
1

На самом начальном шаге мы делаем $%n$% присваиваний; это можно для удобства считать изменением меток. Далее метка вершины 1 становится окончательной, а метки вершин 2, 3, ... , $%n$% могут поменяться при просмотре вершины 1 и исходящих из неё рёбер. Это ещё $%n-1$% изменение. Далее метка вершины 2 меняться не будет, а метки вершин 3, ... , $%n$% могут измениться, что даёт $%n-2$% изменения, и так далее. Общая сумма равна $%1+2+\cdots+n=\frac{n(n+1)}2$%. Это наихудшее значение может достигаться, например, для случая, когда меткой ребра из $%i$%-й вершины в $%j$%-ю служит число $%2|i-j|-1$%. Здесь все оптимальные пути будут проходить через вершины с последовательными номерами, а при любом отклонении результат будет получаться хуже. Метки будут меняться при просмотре каждой очередной вершины, и общее число изменений будет описываться указанной формулой.

ссылка

отвечен 9 Янв '15 19:28

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,094

задан
9 Янв '15 14:40

показан
746 раз

обновлен
9 Янв '15 19:28

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru