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

@Programistka · Регистрация: 12.06.2014

Студворк — интернет-сервис помощи студентам

Задан граф с N вершинами вычислить количество различных путей между всеми парами вершин графа

@Vladimir. · 14.06.2014, 13:11

1. Реализуем операции сложения и умножения матриц (или подключаем boost::uBLAS)
2. Представляем граф матрицей смежности X.
3. Матрица достижимости P = X+X^2+X^3+...+X^(n-1)+X^n
4. Количество всех возможных путей = сумма значений всех элементов P.

@Programistka 0 / 0 / 0 Регистрация: 12.06.2014 Сообщений: 6
		1
	Вычислить количество различных путей между всеми парами вершин графа 13.06.2014, 11:32. Показов 2221. Ответов 1 Метки нет (Все метки) Задан граф с N вершинами вычислить количество различных путей между всеми парами вершин графа 0

@Vladimir. 377 / 228 / 79 Регистрация: 24.11.2009 Сообщений: 695
	14.06.2014, 13:11	2
	1. Реализуем операции сложения и умножения матриц (или подключаем boost::uBLAS) 2. Представляем граф матрицей смежности X. 3. Матрица достижимости P = X+X^2+X^3+...+X^(n-1)+X^n 4. Количество всех возможных путей = сумма значений всех элементов P. 1

Опции темы