Родились сегодня:
ivan_papus


Лидеры

ID: 259041

Алексеев Владимир Николаевич

Мастер-Эксперт

1167

Россия, пос. Теплоозёрск, ЕАО


ID: 405587

Magic2hand

5-й класс

696


ID: 226425

Konstantin Shvetski

Модератор

318

Россия, Северодвинск


ID: 137394

Megaloman

Мастер-Эксперт

181

Беларусь, Гомель


ID: 405604

Ника

Посетитель

141


ID: 400669

epimkin

Профессионал

119


ID: 405537

hipunova1512

Посетитель

88


8.10.4

05.12.2021

JS: 2.10.3
CSS: 4.6.0
jQuery: 3.6.0
DataForLocalStorage: 2021-12-08 21:46:03-standard


Консультации и решение задач по алгебре, геометрии, анализу, дискретной математике.

Администратор раздела: Коцюрбенко Алексей Владимирович (Старший модератор)

Консультация онлайн # 201215

Раздел:  Математика
Автор вопроса: rebzua (Посетитель)
Дата: 23.06.2021, 17:43 Консультация закрыта
Поступило ответов: 1

Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос:
алгоритм Дейкстры
Определить кратчайшие расстояния от начальной вершины ко всем остальным вершинам

-----
Прикрепленные файлы:

Здравствуйте, rebzua!

Исходный граф показан в первом прикреплённом файле.

Определим кратчайшие маршруты из вершины 1 в вершины 2, 3, 4, 5, 6, 7. Присвоим вершине 1 метку, равную 0, а остальным вершинам -- равные бесконечности (inf) (второй прикреплённый файл).

Выберем такую вершину W (сейчас это вершина 1), которая имеет минимальную метку, и рассмотрим все вершины, в которые из вершины W можно попасть напрямую, минуя промежуточные вершины. Каждой из рассмотренных вершин присвоим метку, равную сумме метки W и длины пути из вершины W в рассмотренную вершину, но только в том случае, если полученная сумма меньше предыдущего значения метки. В противном случае оставляем метку прежней (третий прикреплённый файл).

Рассмотрев все вершины, в которые есть прямой путь из W, последнюю отметим как посещённую и выберем из ещё не посещённых вершин такую, которая имеет минимальное значение метки. Эта вершина будет следующей вершиной W. В данном случае это вершина 3. Рассмотрим все вершины, в которые есть есть прямые пути из вершины 3 и которые ешё не помечены как посещённые. Снова определяем сумму метки W и веса ребра из W в текущую вершину и если эта сумма меньше предыдущей метки, то заменяем эту метку на полученную сумму (четвёртый прикреплённый файл).

Отмечаем вершину 3 как посещённую и переходим к вершине 2, которая имеет минимальную метку среди непосещённых вершин. Из вершины 2 есть прямой путь только в вершину 5. Метку этой вершины изменяем на 17 (пятый прикреплённый файл).

Переходя к вершине 4, проделываем аналогичные операции. При этом метка вершины 6, в которую есть прямой путь из вершины 4, останется прежней (шестой прикреплённый файл).

Результат перехода к вершине 6 представлен в седьмом прикреплённом файле, к вершине 5 -- в восьмом прикреплённом файле.

В девятом прикреплённом файле показан конечный результат выполнения всех действий. То есть кратчайший путь из вершины 1 в вершину 2 равен 11, в вершину 3 -- 8, в вершину 4 -- 13, в вершину 5 -- 17, в вершину 6 -- 15, в вершину 7 -- 23.

Гордиенко Андрей Владимирович

Мастер-Эксперт
27.06.2021, 06:15
Мини-форум консультации # 201215
Нет сообщений в мини-форуме
Возможность оставлять сообщения в мини-форумах консультаций доступна только после входа в систему.
Воспользуйтесь кнопкой входа вверху страницы, если Вы зарегистрированы или пройдите простую процедуру регистрации на Портале.

Лучшие эксперты раздела

Алексеев Владимир Николаевич

Мастер-Эксперт

Рейтинг: 1167

Konstantin Shvetski

Модератор

Рейтинг: 318

Коцюрбенко Алексей Владимирович

Старший модератор

Рейтинг: 201

epimkin

Профессионал

Рейтинг: 119

sglisitsyn

6-й класс

Рейтинг: 50

Лангваген Сергей Евгеньевич

Советник

Рейтинг: 45