Задачи на движение
<<  “Скорость, расстояние, время и таинственные отношения между ними” Определение своего местонахождения и направления движения на местности  >>
Алгоритм находит кратчайшее расстояние от одной из вершин графа до
Алгоритм находит кратчайшее расстояние от одной из вершин графа до
Формальное определение
Формальное определение
Инициализация
Инициализация
Первый шаг Минимальную метку имеет вершина 1. Её соседями являются
Первый шаг Минимальную метку имеет вершина 1. Её соседями являются
Первый по очереди сосед вершины 1 — вершина 2, потому что длина пути
Первый по очереди сосед вершины 1 — вершина 2, потому что длина пути
Аналогичную операцию проделываем с двумя другими соседями 1-й
Аналогичную операцию проделываем с двумя другими соседями 1-й
Все соседи вершины 1 проверены
Все соседи вершины 1 проверены
Второй шаг Шаг алгоритма повторяется
Второй шаг Шаг алгоритма повторяется
Первый (по порядку) сосед вершины 2 — вершина 1. Но она уже посещена,
Первый (по порядку) сосед вершины 2 — вершина 1. Но она уже посещена,
Ещё один сосед вершины 2 — вершина 4. Если идти в неё через 2-ю, то
Ещё один сосед вершины 2 — вершина 4. Если идти в неё через 2-ю, то
Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и
Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и
Третий шаг
Третий шаг
Дальнейшие шаги
Дальнейшие шаги
Дальнейшие шаги
Дальнейшие шаги
Завершение выполнения алгоритма Алгоритм заканчивает работу, когда
Завершение выполнения алгоритма Алгоритм заканчивает работу, когда
Псевдокод
Псевдокод
Картинки из презентации «Алгоритм находит кратчайшее расстояние от одной из вершин графа до всех остальных» к уроку математики на тему «Задачи на движение»

Автор: ADMIN. Чтобы познакомиться с картинкой полного размера, нажмите на её эскиз. Чтобы можно было использовать все картинки для урока математики, скачайте бесплатно презентацию «Алгоритм находит кратчайшее расстояние от одной из вершин графа до всех остальных.pps» со всеми картинками в zip-архиве размером 277 КБ.

Алгоритм находит кратчайшее расстояние от одной из вершин графа до всех остальных

содержание презентации «Алгоритм находит кратчайшее расстояние от одной из вершин графа до всех остальных.pps»
Сл Текст Сл Текст
1Алгоритм находит кратчайшее расстояние 8соединяющего u с этим соседом. Если
от одной из вершин графа до всех полученное значение длины меньше значения
остальных. Алгоритм работает только для метки соседа, заменим значение метки
графов без рёбер отрицательного веса. полученным значением длины. Рассмотрев
Алгоритм широко применяется в всех соседей, пометим вершину u как
программировании и технологиях, например, посещенную и повторим шаг алгоритма. 8.
его использует протокол OSPF для 9Первый шаг Минимальную метку имеет
устранения кольцевых маршрутов. Алгоритм вершина 1. Её соседями являются вершины 2,
Дейкстры — алгоритм на графах, 3 и 6. 9.
изобретённый нидерландским ученым Э. 10Первый по очереди сосед вершины 1 —
Дейкстрой в 1959 году. 1. вершина 2, потому что длина пути до неё
2OSPF (англ. Open Shortest Path First) минимальна. Длина пути в неё через вершину
— протокол динамической маршрутизации, 1 равна сумме кратчайшего расстояния до
основанный на технологии отслеживания вершины 1, значение её метки, и длины
состояния канала (link-state technology) и ребра, идущего из 1-ой в 2-ую, то есть 0 +
использующий для нахождения кратчайшего 7 = 7. Это меньше текущей метки вершины 2,
пути Алгоритм Дейкстры (Dijkstra’s бесконечности, поэтому новая метка 2-й
algorithm). Протокол OSPF был разработан вершины равна 7. 10.
IETF в 1988 году. Последняя версия 11Аналогичную операцию проделываем с
протокола представлена в RFC 2328. двумя другими соседями 1-й вершины — 3-й и
Протокол OSPF представляет собой протокол 6-й. 11.
внутреннего шлюза (Interior Gateway 12Все соседи вершины 1 проверены.
Protocol — IGP). Протокол OSPF Текущее минимальное расстояние до вершины
распространяет информацию о доступных 1 считается окончательным и пересмотру не
маршрутах между маршрутизаторами одной подлежит. Вычеркнем её из графа, чтобы
автономной системы. 2. отметить, что эта вершина посещена. 12.
3OSPF предлагает решение следующих 13Второй шаг Шаг алгоритма повторяется.
задач: Оптимальное использование Снова находим «ближайшую» из непосещенных
пропускной способности (т.к. строится вершин. Это вершина 2 с меткой 7. Соседями
минимальный остовный граф по алгоритму вершины 2 являются вершины 1, 3 и 4. 13.
Дейкстры); Метод выбора пути; Увеличение 14Первый (по порядку) сосед вершины 2 —
скорости сходимости (в сравнении с вершина 1. Но она уже посещена, поэтому с
протоколом RIP2, так как нет необходимости 1-й вершиной ничего не делаем. Следующий
выжидания многократных тайм-аутов по 30с); сосед вершины 2 — вершина 3, так имеет
Поддержка сетевых масок переменной длины минимальную метку из вершин, отмеченных
(VLSM); Достижимость сети (быстро как не посещённые. Если идти в неё через
обнаруживаются отказавшие маршрутизаторы, 2, то длина такого пути будет равна 17 (7
и топология сети изменяется + 10 = 17). Но текущая метка третьей
соответствующим образом). 3. вершины равна 9<17, поэтому метка не
4Варианты задач для алгоритма Дейкстры. меняется. 14.
Вариант 1. Дана сеть автомобильных дорог, 15Ещё один сосед вершины 2 — вершина 4.
соединяющих города некоторой области. Если идти в неё через 2-ю, то длина такого
Некоторые дороги односторонние. Найти пути будет равна сумме кратчайшего
кратчайшие пути от города а до каждого расстояние до 2-ой вершины и расстояния
города области (если двигаться можно между вершинами 2 и 4, то есть 22 (7 + 15
только по дорогам). Вариант 2. Имеется = 22). Поскольку 22<, устанавливаем
некоторое количество авиарейсов между метку вершины 4 равной 22. 15.
городами мира, для каждого известна 16Все соседи вершины 2 просмотрены,
стоимость. Стоимость перелёта из A в B замораживаем расстояние до неё и помечаем
может быть не равна стоимости перелёта из её как посещенную. 16.
B в A. Найти маршрут минимальной стоимости 17Третий шаг. Повторяем шаг алгоритма,
(возможно, с пересадками) от Копенгагена выбрав вершину 3. После её «обработки»
до Барнаула. 4. получим такие результаты: 17.
5Формальное определение. Дан взвешенный 18Дальнейшие шаги. Повторяем шаг
ориентированный граф G(V,E) без петель и алгоритма для оставшихся вершин. Это будут
дуг отрицательного веса. Найти кратчайшие вершины 6, 4 и 5, соответственно порядку.
пути от некоторой вершины 1 графа G до 18.
всех остальных вершин этого графа. 5. 19Завершение выполнения алгоритма
6Описание алгоритма. Каждой вершине из Алгоритм заканчивает работу, когда
V сопоставим метку — минимальное известное вычеркнуты все вершины. Результат его
расстояние от этой вершины до 1. Алгоритм работы виден на последнем рисунке:
работает пошагово — на каждом шаге он кратчайший путь от вершины 1 до 2-й
«посещает» одну вершину и пытается составляет 7, до 3-й — 9, до 4-й — 20, до
уменьшать метки. Работа алгоритма 5-й — 20, до 6-й — 11. 19.
завершается, когда все вершины посещены. 20Обозначения V — множество вершин графа
6. E — множество ребер графа w[ij] — вес
7Инициализация. Метка самой вершины 1 (длина) ребра ij a — вершина, расстояния
полагается равной 0, метки остальных от которой ищутся U — множество посещенных
вершин — бесконечности. Это отражает то, вершин d[u] — по окончании работы
что расстояния от 1 до других вершин пока алгоритма равно длине кратчайшего пути из
неизвестны. Все вершины графа помечаются a до вершины u p[u] — по окончании работы
как непосещённые. 7. алгоритма содержит кратчайший путь из a в
8Шаг алгоритма. Если все вершины u. 20.
посещены, алгоритм завершается. В 21Псевдокод. 21.
противном случае, из ещё не посещённых 22Альтернативные алгоритмы Алгоритм
вершин выбирается вершина u, имеющая Беллмана-Форда – решение той же задачи,
минимальную метку. Мы рассматриваем если граф может содержать и рёбра
всевозможные маршруты, в которых u отрицательного веса Алгоритм
является предпоследним пунктом. Вершины, в Флойда-Уоршелла – поиск кратчайших
которые ведут рёбра из u, назовем соседями расстояний между всеми парами вершин
этой вершины. Для каждого соседа вершины Алгоритм Джонсона – позволяет найти
u, кроме отмеченных как посещённые, кратчайшие пути между всеми парами вершин
рассмотрим новую длину пути, равную сумме взвешенного ориентированного графа при
значений текущей метки u и длины ребра, отсутствии циклов. 22.
Алгоритм находит кратчайшее расстояние от одной из вершин графа до всех остальных.pps
http://900igr.net/kartinka/matematika/algoritm-nakhodit-kratchajshee-rasstojanie-ot-odnoj-iz-vershin-grafa-do-vsekh-ostalnykh-240824.html
cсылка на страницу

Алгоритм находит кратчайшее расстояние от одной из вершин графа до всех остальных

другие презентации на тему «Алгоритм находит кратчайшее расстояние от одной из вершин графа до всех остальных»

«Решение алгоритмов» - Пара взаимно-двойственных задач линейного программирования. Задача поиска направления корректировки. Прогноз шага корректировки. Метод сопряженных направлений. Прямо-двойственные алгоритмы. Параметры управления алгоритмом. 1984 – полиномиальный МВТ (Кармаркар). Аффинно-масштабирующие алгоритмы внутренних точек.

«Алгоритмы» - Немного о происхождении. Линейный алгоритм. К о л о б о к. Разветвленные. То сам упадёшь. Сказка закончилась счастливо. Дед бил-бил, не разбил. Содержание. Дед плачет, баба плачет, Результаты исследования Заключение. В словесном описании разветвленного алгоритма используются слова "если", "то", "иначе".

«Граф» - Рёбра графа. На рисунке изображен граф, хорошо знакомый жителям нашего города. Применение графов. С берегов на острова были перекинуты мосты. Сколько всего рукопожатий было сделано? Родословная моей семьи. Пайдда. Типичными графами являются схемы авиалиний, которые часто вывешивается в аэропортах. Исследовать роль графов в нашей жизни.

«Урок Скорость время расстояние» - Скорость. Мотоциклист ехал 3 ч со средней скоростью 60 км/ч и 2 ч со средней скоростью 70 км/ч. Расстояние – S (км, м, дм, см) Время - ? (сут., ч, мин, с) Скорость – ? (км/ч, км/мин, м/с). Время. Однако обратный перелет занимает 80 мин. Расположи числа в порядке возрастания и составь слово из слогов.

«Расстояние от точки до прямой» - В единичном кубе A…D1 найдите расстояние от точки A до прямой BA1. 2. Треугольник ABC – равнобедренный, AC = BC. 4. Треугольник ABC – произвольный. В единичном кубе A…D1 найдите расстояние от точки A до прямой CD1. В единичном кубе A…D1 найдите расстояние от точки A до прямой CB1. В единичном кубе A…D1 найдите расстояние от точки A до прямой DD1.

«Короткое замыкание» - Сильный нагрев проводов может привести к возгоранию изоляции и к пожару. Существуют разные виды предохранителей. 1. Самый простой вид - плавкая вставка. Перегоревшую пробку меняют на новую. Есть такое выражение "перегорели пробки". Плавкие предохранители. Условное обозначение предохранителя на электрической схеме:

Задачи на движение

18 презентаций о задачах на движение
Урок

Математика

71 тема
Картинки
900igr.net > Презентации по математике > Задачи на движение > Алгоритм находит кратчайшее расстояние от одной из вершин графа до всех остальных