После k шагов алгоритм Дейкстры определил кратчайшие расстояния до k вершин графа из общего количества n.Какое количество шагов в лучшем и худшем случае нужно сделать алгоритму Дейкстры, чтобы найти все кратчайшие расстояния?

Сам алгоритм Дейкстры:

Инициализация. Метка самой вершины a полагается равной 0, метки остальных вершин — бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае из еще не посещенных вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, соединенные с вершиной u ребрами, назовем соседями этой вершины. Для каждого соседа рассмотрим новую длину пути, равную сумме текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученная длина меньше метки соседа, заменим метку этой длиной. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг.

Изображение 1 Изображение 2

задан 4 Янв 19:32

изменен 5 Янв 16:43

@abaranci: превосходно, что Вы дали описание реализации алгоритма. Без него никакой разговор был бы невозможен. Осталось пояснить, что понимается под "шагом" алгоритма.

(5 Янв 14:03) falcao

@falcao в описании алгоритма описан,что такое шаг алгоритма

(5 Янв 14:27) abaranci

@abaranci: да, действительно. Я как-то не заметил этого заголовка. Но тогда получается, что на каждом шаге появляется одна посещённая вершина. Значит, всего шагов должно быть n, и это значение ни от чего не зависит. За счёт чего тогда число дальнейших шагов может меняться?

(5 Янв 14:49) falcao

@falcao Вот я тоже не очень понял почему количество шагов может быть отлично от N. Во время теста я подумал о том, что может быть шаги на которых не нужно помечать соседние и вычислять длину пути не считаются как шаг, но это глупо наверное. (Я имел ввиду случай как на изображении 1 и 2 которые я добавил в вопросе. На изображении 1 вершина H была включена в основное дерево на последнем шаге. И получилось так что вершины Z и G можно просто добавить в основное дерево без <<дополнительных вычислений>> перед этим

(5 Янв 16:06) abaranci

@abaranci: я не обладаю способностями к правильному угадыванию, поэтому даже не берусь никогда домысливать. Наверное, тут что-то вполне конкретное имелось в виду, и я не исключаю, что могло подразумеваться то число шагов, после которых у всех вершин установились окончательные метки. Но лучше всё-таки уточнить у того, кто ставил эту задачу.

(5 Янв 16:27) falcao

@falcao Вопрос был с подвохом." Ответ преподавателя: Ответ правильный. Вопрос был специально поставлен так, чтобы отвечающий задумался и принял правильное решение. Для этого достаточно знать, что на каждом шаге алгоритма находится ровно одна вершина, до которой кратчайшее расстояние найдено."

(5 Янв 22:50) abaranci

@abaranci: я считаю, что задавать такие вопросы намеренно -- это "злодеяние" :) Конечно, эти слова относятся не к Вам, а к преподавателю. "Заставить задуматься" -- это хорошо, когда в процессе узнаётся что-то новое. Если же результатом раздумий является "принятие" того, что "кастрюля -- это кастрюля", то полезного в этом нет ничегошеньки. Получается, что зря потеряли время. Не говоря о том, что есть куча похожих задач, где алгоритм на самом деле что-то находит быстрее или медленнее. Возникают сомнения, то есть самое плохое, что только может быть.

(5 Янв 22:58) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×999
×566

задан
4 Янв 19:32

показан
186 раз

обновлен
5 Янв 22:58

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

по почте:

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

по RSS:

Ответы

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

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