Как в python реализовать вычисление матрицы расстояний методом возведения матрицы смежности в степень? Мне нужно реализовать вычисление матрицы расстояний методом возведения матрицы смежности в степень. На вход подается граф, на выход - матрица дистанций (список списков целых чисел). Подскажите как получить матрицу расстояний?
У меня получается найти только матрицу смежности:import networkx as nx
from networkx import DiGraph
digraph = DiGraph()
for node_val in range(1, 8):
digraph.add_node(node_val)
digraph.add_edge(1, 2)
digraph.add_edge(1, 3)
digraph.add_edge(1, 4)
digraph.add_edge(2, 4)
digraph.add_edge(2, 5)
digraph.add_edge(3, 6)
digraph.add_edge(4, 3)
digraph.add_edge(4, 6)
digraph.add_edge(4, 7)
digraph.add_edge(5, 4)
digraph.add_edge(5, 7)
digraph.add_edge(7, 6)
adj_matrix_sparse = nx.adjacency_matrix(digraph)
adj_matrix_dense = adj_matrix_sparse.todense()
print(adj_matrix_dense)
Как в python реализовать вычисление матрицы расстояний методом возведения матрицы смежности в степень? Мне нужно реализовать вычисление матрицы расстояний методом возведения матрицы смежности в степень. На вход подается граф, на выход - матрица дистанций (список списков целых чисел). Подскажите как получить матрицу расстояний?
У меня получается найти только матрицу смежности:import networkx as nx
from networkx import DiGraph
digraph = DiGraph()
for node_val in range(1, 8):
digraph.add_node(node_val)
digraph.add_edge(1, 2)
digraph.add_edge(1, 3)
digraph.add_edge(1, 4)
digraph.add_edge(2, 4)
digraph.add_edge(2, 5)
digraph.add_edge(3, 6)
digraph.add_edge(4, 3)
digraph.add_edge(4, 6)
digraph.add_edge(4, 7)
digraph.add_edge(5, 4)
digraph.add_edge(5, 7)
digraph.add_edge(7, 6)
adj_matrix_sparse = nx.adjacency_matrix(digraph)
adj_matrix_dense = adj_matrix_sparse.todense()
print(adj_matrix_dense)
У меня получается найти только матрицу смежности:import networkx as nx
from networkx import DiGraph
digraph = DiGraph()
for node_val in range(1, 8):
digraph.add_node(node_val)
digraph.add_edge(1, 2)
digraph.add_edge(1, 3)
digraph.add_edge(1, 4)
digraph.add_edge(2, 4)
digraph.add_edge(2, 5)
digraph.add_edge(3, 6)
digraph.add_edge(4, 3)
digraph.add_edge(4, 6)
digraph.add_edge(4, 7)
digraph.add_edge(5, 4)
digraph.add_edge(5, 7)
digraph.add_edge(7, 6)
adj_matrix_sparse = nx.adjacency_matrix(digraph)
adj_matrix_dense = adj_matrix_sparse.todense()
print(adj_matrix_dense)
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Для вычисления матрицы расстояний методом возведения матрицы смежности в степень вам потребуется использовать библиотеку numpy. Вот как это можно сделать:
import numpy as np# Преобразование матрицы смежности в матрицу дистанций
def distance_matrix(adj_matrix):
num_nodes = len(adj_matrix)
distances = np.array(adj_matrix)
for i in range(2, num_nodes + 1):
distances = np.dot(distances, adj_matrix)
for j in range(num_nodes):
for k in range(num_nodes):
if distances[j][k] > 0:
distances[j][k] = 1
return distances
# Преобразование матрицы смежности в обычный список списков
def adjacency_matrix_to_list(adj_matrix):
adjacency_list = adj_matrix.tolist()
return adjacency_list
# Создание матрицы смежности из графа
adj_matrix_sparse = nx.adjacency_matrix(digraph)
adj_matrix_dense = adj_matrix_sparse.todense().tolist()
# Вычисление матрицы расстояний
distance_matrix = distance_matrix(adj_matrix_dense)
print(distance_matrix)
Этот код сначала определяет функцию distance_matrix, котор принимает матрицу смежности в виде numpy.ndarray и возвращает матрицу расстояний. Далее определяется функция adjacency_matrix_to_list, котор преобразует матрицу смежность в обычный список списков. Затем создается матрица смежности из графа и вычисляется матрица расстояний с использованием функции distance_matrix. Результат выводится на экран.