Ориентированный граф задан с помощью матрицы расстояний. Бесплатный доступ к контрольной работе

Реферат.Справочник
Контрольные работы по высшей математике
Ориентированный граф задан с помощью матрицы расстояний

Ориентированный граф задан с помощью матрицы расстояний .pdf

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

Условие

Ориентированный граф задан с помощью матрицы расстояний. 1) Построить ориентированный граф, соответствующий данной матрице расстояний. 2) Используя алгоритм нахождения кратчайшего пути (не перебор вариантов!), найти кратчайший путь из вершины S в вершину T. В ответе указать длину кратчайшего пути и последовательность вершин, составляющих кратчайший путь. Начальная вершина Конечная вершина A B C D E F T S 7 8 9 A 8 7 B 8 9 4 C 7 9 D 5 E 8 F 6

Решение

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

Построим граф:
Последовательно будем находить минимальные расстояния из вершины S в следующие вершины:
Шаг №1
S→A=7
S→B=8
S→C=9
Шаг №2
S→D=minS→A→D;S→B→D=min15;16=15
S→E=minS→B→E=17
S→F=minS→A→F,S→B→F,S→C→F=min14;12;18=12
Шаг №3
S→T=minS→D→T,S→E→T,S→F→T=min{15+5;17+8;12+6}=
=min{20;25;18}=18
S→T=S→F→T=S→B→F→T

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

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

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