Определите чему будет равно значение P[2] в алгоритме Дейкстры. Бесплатный доступ к контрольной работе

Реферат.Справочник
Контрольные работы по информационным технологиям
Определите чему будет равно значение P[2] в алгоритме Дейкстры

Определите чему будет равно значение P[2] в алгоритме Дейкстры .pdf

Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥

Условие

Определите, чему будет равно значение P[2] в алгоритме Дейкстры, если источником является вершина c (узел а – 1-ый в нумерации узлов, … узел e – 5-ый)

Решение

Потяни, чтобы посмотреть

Алгоритм Дейкстры (Dijkstra’s algorithm) — алгоритм на графах, находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без ребер отрицательного веса.
Шаг 0:
Установим расстояние для начальной вершины d(3)=0
Шаг 1:
Непомеченные вершины V={1;2;3;4;5;}
Минимальные расстояния до непомеченных вершин d={∞;∞;0;∞;∞;}
Убираем вершину 3 c наименьшим расстоянием 0 из множества V
Установим v*=3
Рассмотрим смежные вершины с вершиной v*=3:
d(1)>d(v*)+d(v*;1)=0+3=3=>d(1)=3
Теперь оптимальный путь от 3 до 1: 3-1
d(2)>d(v*)+d(v*;2)=0+7=7=>d(2)=7
Теперь оптимальный путь от 3 до 2: 3-2
d(4)>d(v*)+d(v*;4)=0+3=3=>d(4)=3
Теперь оптимальный путь от 3 до 4: 3-4
Новые расстояния: d={3;7;3;∞;}
Шаг 2:
Непомеченные вершины V={1;2;4;5;}
Минимальные расстояния до непомеченных вершин d={3;7;3;∞;}
Убираем вершину 1 c наименьшим расстоянием 3 из множества V
Установим v*=1
Рассмотрим смежные вершины с вершиной v*=1:
d(5)>d(v*)+d(v*;5)=3+9=12=>d(5)=12
Теперь оптимальный путь от 3 до 5: 3-1-5
Новые расстояния: d={7;3;12;}
Шаг 3:
Непомеченные вершины V={2;4;5;}
Минимальные расстояния до непомеченных вершин d={7;3;12;}
Убираем вершину 4 c наименьшим расстоянием 3 из множества V
Установим v*=4
Рассмотрим смежные вершины с вершиной v*=4:
d(2)>d(v*)+d(v*;2)=3+3=6=>d(2)=6
Теперь оптимальный путь от 3 до 2: 3-4-2
d(5)>d(v*)+d(v*;5)=3+3=6=>d(5)=6
Теперь оптимальный путь от 3 до 5: 3-4-5
Новые расстояния: d={6;6;}
P[2]=4

50% задачи недоступно для прочтения

Переходи в Кампус, регистрируйся и получай полное решение

Получить задачу