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