Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ:  Археология Биология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия ЭкологияТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву 
Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Задача нахождения кратчайшего пути в моделях на графахПоиск на нашем сайте Математическая постановка задачи: Дан взвешенный ориентированный граф G(V,E) без петель и дуг отрицательного веса. Найти кратчайшие пути от некоторой вершины a графа G до всех остальных вершин этого графа. Алгори́тм Де́йкстры Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов. Каждой вершине из V сопоставим метку — минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово — на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.21. Задача построения кратчайших путей между всеми парами вершин. Алгоритм Флойда Задача о кратчайшем пути между всеми парами вершин: Требуется найти кратчайший путь из каждой вершины u в каждую вершину v Алгоритм Флойда: Пусть вершины графа Существует два варианта значения 1.Кратчайший путь между 2.Существует более короткий путь между Таким образом, для нахождения значения функции достаточно выбрать минимум из двух обозначенных значений. Тогда рекуррентная формула для
Алгоритм Флойда-Уоршелла последовательно вычисляет все значения
|
||
|
|
Последнее изменение этой страницы: 2024-07-06; просмотров: 35; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 216.73.217.110 (0.005 с.) |
пронумерованы от 1 до 
и введено обозначение 
(i<j<k) для длины кратчайшего пути от 
до 
, который кроме самих вершин 
проходит только через вершины 
. Очевидно, что 
— длина (вес) ребра 
, если таковое существует (в противном случае его длина может быть обозначена как 
).
:
, тогда 
для 
являются длинами кратчайших путей между вершинами 
