Задача о кратчайшем пути

Сентябрь 13, 2022

Главная
Математика
Задача о кратчайшем пути

Содержание

2. Задача о кратчайшем пути Пусть G =(V, E) – н-граф. Пусть каждому ребру e графа приписано
3. Алгоритм Присвоим всем вершинам метки s(v)=+∞, причем метка s(а)=0 Проверим каждое ребро (vi , vj) на
4. Алгоритм Совершаем пересчет меток до тех пор, пока не перестанет выполнятся указанное условие. Метка, которую получила
6. Скачать презентацию

Слайд 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 является длиной искомого маршрута.