Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






  • Орсети, кратчайшие пути, алгоритм Дейкстры.






    Ориентированная сеть (орсеть) – связный граф с положительными весами на дугах.

    Если в сети существует вершина, из которой достижимы все остальные вершины, то сеть называется корневой, а вершина – корнем.

    Вес сети – сумма весов всех дуг сети.

    Кратчайший путь – путь, сумма весов дуг которого наименьшая из всех путей из корня до вершины.

    Алгоритм Дейкстры.

    1)Положим метку , метки всех остальных вершин .?

    Множество окрашенных вершин .?

    2)Пересчитываются метки всех неокрашенных вершин :

    , среди них выбираются вершины с наименьшей меткой и окрашиваются одна из дуг , которая инцидентна.

    3)Если все вершины окрашены, то конец алгоритма – длина кратчайшего пути, окрашенные дуги – длина кратчайшего пути; в противном случае переходим к шагу 2.






    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.