Я знаю, что вычислительная стоимость матрицы смежности равна n * n. А именно, эта теоретико-графическая структура содержит значение 0 или 1 для каждой пары вершин, если существует ребро или нет, поэтому ему нужно n ^ 2 пробела. Меня интересует вычислительная стоимость матрицы расстояний на основе смежности, в которой каждая запись представляет собой евклидово расстояние между строками матрицы смежности. Эта матрица является матрицей псевдодальности, поскольку она может содержать ноль в недиагональных местах, если две строки смежности идентичны.
Например, у нас есть граф путей с пятью вершинами, матрица смежности которых выглядит следующим образом:
1 2 3 4 5
1 0 1 0 0 0
2 1 0 1 0 0
3 0 1 0 1 0
4 0 0 1 0 1
5 0 0 0 1 0
Затем мы вычисляем матрицу расстояний евклидовых расстояний между строками вышеуказанной матрицы смежности. Эта матрица расстояний имеет вид:
1 2 3 4 5
1 0.00 1.73 1 1.73 1.41
2 1.73 0.00 2 1.41 1.73
3 1.00 2.00 0 2.00 1.00
4 1.73 1.41 2 0.00 1.73
5 1.41 1.73 1 1.73 0.00
Меня интересует вычислительная стоимость вычисления матрицы расстояний и вычислительная стоимость всего процесса.
Мы создадим граф путей с пятью узлами в igraph R следующим образом:
path=graph.formula(1-2,2-3,3-4,4-5)
Далее мы генерируем матрицу смежности:
adj.matrix=as.matrix(get.adjacency(path))
А мы рассчитаем матрицу расстояний евклидовых расстояний между строками матрицы смежности:
dist.matrix=as.matrix(dist(adj.matrix)).
Меня интересует вычислительная стоимость приведенных выше расчетов.