Дан граф с вершинами Е, В, А, Г, Д, Б. Алгоритм:
-
Из вершины Б можно пойти в вершины А, Г, Д.
Б—А = 6. Вес вершины А — 6.
Б—Г = 4. Вес вершины Г — 4.
Б—Д = 2. Вес вершины Д — 2. -
Из вершины Г можно пойти в вершину А.
Б—Г—А = ___, тогда путь Б—Г—А ___ , чем Б—А. Вес вершины А — 5. -
Из вершины А можно попасть в Е. Вес вершины Е равен 9. И в вершину В. Вес вершины В — 7.
-
Из вершины Д можно пройти в В и Б.
Вес вершины В — ___ . Если из В идти в Е, то вес вершины Е будет равен ___ .
Варианты ответа (выбрать путь): Б—Д—В—Е; Б—Г—А—Е; Б—А—В—Е.
Текст самого вопроса на фото не виден. Судя по алгоритму, нужно выбрать кратчайший путь из Б в Е.
Рёбра графа определяем по шагам алгоритма: Б—А =
Шаг
Шаг
Шаг
Сравним три пути из Б в Е:
Наименьший путь — Б—Г—А—Е.
Алгоритм Дейкстры: у каждой вершины хранится наименьший найденный вес пути от начальной вершины. Он обновляется, только если новый путь короче.
Заполненные пропуски: Б—Г—А =
Кратчайший путь: Б—Г—А—Е, его длина
