алгоритм дейкстры

PPTX 27 sahifa 1,1 MB Bepul yuklash

27 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 1,1 MB

Fayl turi PPTX

Sahifalar 27

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 27

алогритм дейкстры алогритм дейкстры алгоритм дейкстры — алгоритм на графах, изобретённый нидерландским ученым э. дейкстрой в 1959 году. находит кратчайшее расстояние от одной из вершин графа до всех остальных. алгоритм работает только для графов без рёбер отрицательного веса. алгоритм широко применяется в программировании и технологиях, например, его использует протокол ospf для устранения кольцевых маршрутов. пример 1 необходимо найти все кратчайшие пути от вершины №1 для графа, представленного на рисунке: составим матрицу длин кратчайших дуг для данного графа cтартовая вершина, от которой строится дерево кратчайших путей - вершина 1. задаем стартовые условия: d(1)=0, d(x)=∞ окрашиваем вершину 1, y=1. находим ближайшую вершину к окрашенной нами, испоьзуя формулу d(x)=min{d(x); d(y)+ ay,x} d(2)=min{d(2);d(1)+a(1,2)}=min{∞;0+10}=10 d(3)=min{d(3);d(1)+a(1,3)}=min{∞;0+18}=18 d(4)=min{d(4);d(1)+a(1,4)}=min{∞;0+8}=8 d(5)=min{d(5);d(1)+a(1,5)}=min{∞;0+∞}=∞ d(6)=min{d(6) ; d(1)+a(1,6)}=min{∞; 0+∞}=∞ минимальную длину имеет путь от вершины 1 до вершины 4 d(4)=8. включаем вершину №4 в текущее ориентированноe дерево, а так же дугу ведущую в эту вершину. согласно выражению это дуга (1,4) d(2)=min{d(2);d(4)+a(4,2)}=min{10;8+9}=10 d(3)=min{d(3);d(4)+a(4,3)}=min{18;8+∞}=18 d(5)=min{d(5);d(4)+a(4,5)}=min{∞;8+∞}=∞ …

2 / 27

ршины 1 до вершины 6 d(6)=20. включаем вершину №6 в текущее ориентированноe дерево, а так же дугу ведущую в эту вершину. согласно выражению это дуга (4,6) d(5)=min{d(5) ; d(6)+a(6,5)}=min{31; 20+23}=31 минимальную длину имеет путь от вершины 1 до вершины 5 d(5)=31. включаем вершину №5 в текущее ориентированноe дерево, а так же дугу ведущую в эту вершину. согласно выражению это дуга (2,5) ориентированное дерево с корнем в вершине №1 пример 2 рассмотрим выполнение алгоритма на примере графа, показанного на рисунке. пусть требуется найти расстояния от 1-й вершины до всех остальных. кружками обозначены вершины, линиями — пути между ними (ребра графа). в кружках обозначены номера вершин, над ребрами обозначена их «цена» — длина пути. рядом с каждой вершиной красным обозначена метка — длина кратчайшего пути в эту вершину из вершины 1. первый шаг рассмотрим шаг алгоритма дейкстры для нашего примера. минимальную метку имеет вершина 1. её соседями являются вершины 2, 3 и …

3 / 27

иной ничего не делаем. следующий сосед вершины 2 — вершина 3, так как имеет минимальную метку из вершин, отмеченных как не посещённые. если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). но текущая метка третьей вершины равна 9 d[v]+w[vu], то изменим d[u] ← d[v]+w[vu] изменим p[u] ← p[v], u описание в простейшей реализации для хранения чисел d[i] можно использовать массив чисел, а для хранения принадлежности элемента множеству u — массив булевых переменных. в начале алгоритма расстояние для начальной вершины полагается равным нулю, а все остальные расстояния заполняются большим положительным числом (бо́льшим максимального возможного пути в графе). массив флагов заполняется нулями. затем запускается основной цикл. на каждом шаге цикла мы ищем вершину с минимальным расстоянием и флагом равным нулю. затем мы устанавливаем в ней флаг в 1 и проверяем все соседние с ней вершины. если в ней расстояние больше, чем сумма расстояния …

4 / 27

5 / 27

Ko'proq o'qimoqchimisiz?

Barcha 27 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"алгоритм дейкстры" haqida

алогритм дейкстры алогритм дейкстры алгоритм дейкстры — алгоритм на графах, изобретённый нидерландским ученым э. дейкстрой в 1959 году. находит кратчайшее расстояние от одной из вершин графа до всех остальных. алгоритм работает только для графов без рёбер отрицательного веса. алгоритм широко применяется в программировании и технологиях, например, его использует протокол ospf для устранения кольцевых маршрутов. пример 1 необходимо найти все кратчайшие пути от вершины №1 для графа, представленного на рисунке: составим матрицу длин кратчайших дуг для данного графа cтартовая вершина, от которой строится дерево кратчайших путей - вершина 1. задаем стартовые условия: d(1)=0, d(x)=∞ окрашиваем вершину 1, y=1. находим ближайшую вершину к окрашенной нами, испоьзуя формулу d(x)=min{d(x); d(y)+ ay,x}...

Bu fayl PPTX formatida 27 sahifadan iborat (1,1 MB). "алгоритм дейкстры"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: алгоритм дейкстры PPTX 27 sahifa Bepul yuklash Telegram