Question

Для графа с весами: qAB=10, qAC=18, qAD – не задан, qAE=14, qBC=12, qBD=20, qBE – не задан, qCD=6, qCE=14, qDE=10 найти кратчайшие расстояния между всеми вершинами. С помощью полученных кратчайших расстояний между всеми вершинами исходного графа сформировать полный граф.

Answer 1

Пошаговое объяснение:

оуовлалклууллулууллу

Answer 2

Для нахождения кратчайших расстояний между всеми вершинами исходного графа, мы можем воспользоваться алгоритмом Флойда-Уоршалла. Этот алгоритм позволяет найти кратчайшие пути между всеми парами вершин во взвешенном графе.

Для начала создадим матрицу смежности для графа с заданными весами:

mathematicaCopy code
    A   B   C   D   E
A   0  10  18   ?  14
B  10   0  12  20   ?
C  18  12   0   6  14
D   ?  20   6   0  10
E  14   ?  14  10   0

Теперь применим алгоритм Флойда-Уоршалла для поиска кратчайших расстояний между всеми парами вершин. Заполним матрицу кратчайших расстояний:

mathematicaCopy code
    A   B   C   D   E
A   0  10  12  16  14
B  10   0  12  16  26
C  12  12   0   6  14
D  16  16   6   0  10
E  14  26  14  10   0

Теперь мы знаем кратчайшие расстояния между всеми парами вершин исходного графа. Теперь давайте создадим полный граф, используя эти расстояния в качестве весов ребер. Получившийся полный граф будет выглядеть следующим образом:

mathematicaCopy code
    A   B   C   D   E
A   0  10  12  16  14
B  10   0  12  16  26
C  12  12   0   6  14
D  16  16   6   0  10
E  14  26  14  10   0

Теперь у нас есть полный граф с кратчайшими расстояниями между всеми вершинами исходного графа в качестве весов ребер.