Задача о кратчайшем пути - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Задача о кратчайшем пути. Доклад-сообщение содержит 5 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Дискретная математика Задача о кратчайшем пути

Слайд 2

Описание слайда:

Задача о кратчайшем пути Пусть G =(V, E) – н-граф. Пусть каждому ребру e графа приписано положительное число – длина ребра L(e). Задача заключается в нахождении маршрута от вершины a к вершине b, наименьшей длины.

Слайд 3

Описание слайда:

Алгоритм Присвоим всем вершинам метки s(v)=+∞, причем метка s(а)=0 Проверим каждое ребро (vi , vj) на выполнение условия: s(vj) - s(vi) > L(vi , vj). Если это так, пересчитаем метку конца ребра: s(vj) = s(vi)+L(vi , vj).

Слайд 4

Описание слайда:

Алгоритм Совершаем пересчет меток до тех пор, пока не перестанет выполнятся указанное условие. Метка, которую получила вершина b является длиной искомого маршрута.