Кратчайшее расстояние Найди кратчайший путь из Б в Е. Двигаться можно только по вершинам, между которыми есть рёбра. Алгоритм: 1. Из вершины Б можно пойти в вершины А, Г, Д Б-А = 6. Вес вершины А — 6 Б-Г = 4. Вес вершины Г — 4 Б-Д = 2. Вес вершины Д — 2 2. Из вершины Г можно пойти в вершину А. Б-Г-А = тогда путь Б-Г-А , чем Б-А. Вес вершины А = 5 3. Из вершины А можно попасть в Е. Вес вершины Е равен 9. И в вершину В. Вес вершины В — 7. 4. Из вершины Д можно пройти в В и Б. Вес вершины В = . Если из В идти в Е, то вес вершины Е будет равен . Значит, самый короткий путь: Б-Д-В-Е Б-Г-А-Е Б-А-В-Е

Для нахождения кратчайшего пути из вершины Б в вершину Е, нам необходимо проанализировать доступные пути и выбрать путь с наименьшей суммой весов рёбер. Дано: - Б-А = 6 - Б-Г = 4 - Б-Д = 2 - Г-А = 5 - А-Е = 9 - А-В = 7 - Д-В = ? (Не указано, но обозначим как x) - В-Е = ? (Не указано, но обозначим как y) 1. Путь Б-Д-В-Е: - Б-Д = 2 - Д-В = x (неизвестно) - В-Е = y (неизвестно) Сумма весов: 2 + x + y 2. Путь Б-Г-А-Е: - Б-Г = 4 - Г-А = 5 - А-Е = 9 Сумма весов: 4 + 5 + 9 = 18 3. Путь Б-А-В-Е: - Б-А = 6 - А-В = 7 - В-Е = y (неизвестно) Сумма весов: 6 + 7 + y Сравним суммы весов: 1. 2 + x + y 2. 18 3. 6 + 7 + y Таким образом, кратчайшим путем из вершины Б в вершину Е является путь Б-Д-В-Е, если сумма весов на ребрах Д-В и В-Е меньше суммы других вариантов.