Алгоритм Дейкстры: 1. Всем вершинам, за исключением первой, присваивается вес равный бесконечности, а первой вершине – 0. 2. Все вершины не выделены. 3. Первая вершина объявляется текущей.
- Высшая математика
Условие:
Дан взвешенный граф G. Найти кратчайший путь между вершинами графа x6 и x1 методом Дейкстра. Он заключается в том, что вершинам графа присваиваются временные метки, которые затем по определенным правилам заменяются на постоянные метки.
Решение:
Алгоритм Дейкстры: 1. Всем вершинам, за исключением первой, присваивается вес равный бесконечности, а первой вершине 0. 2. Все вершины не выделены. 3. Первая вершина объявляется текущей. 4. Вес всех невыделенных вершин пересчитывается по формуле: вес невыделенной вершины есть минимальное число из старого веса данной вершины, суммы веса текущей вершины и веса ребра, соединяющего текущую вершину с невыделенной. 5. Среди невыделенных вершин ищется вершина с минимальным весом. Если таковая не найдена, то есть вес всех вершин равен бесконечности, то маршрут не существует. Следовательно, выход...
Похожие задачи
Не нашел нужную задачу?
Воспользуйся поиском
AI помощники
Выбери предмет
- Правоохранительные органы
- Пожарная безопасность
- Парикмахерское искусство
- Природообустройство и водопользование
- Почвоведение
- Приборостроение и оптотехника
- Промышленный маркетинг и менеджмент
- Производственный маркетинг и менеджмент
- Процессы и аппараты
- Программирование
- Право и юриспруденция
- Психология
- Политология
- Педагогика
- Трудовое право
- Теория государства и права (ТГП)
- Таможенное право
- Теория игр
- Теория вероятностей
- Теоретическая механика
- Теория управления
- Технология продовольственных продуктов и товаров
- Технологические машины и оборудование
- Теплоэнергетика и теплотехника
- Туризм
- Товароведение
- Таможенное дело
- Торговое дело
- Теория машин и механизмов
- Транспортные средства