Вопрос по c, linear-algebra, matlab – преобразование матрицы смежности в матрицу расстояний или расстояний

4

Привет можно ли преобразовать матрицу смежности из одного и нулей, как определеноВот в матрицу расстояний, как определеноВот  где каждая ссылка будет иметь длину блока 1

да я редактировал квестон pyCthon
У вас есть информация о весе каждой ссылки? Manlio

Ваш Ответ

1   ответ
4

ованного графа. Чтобы получить расстояния между любыми двумя вершинами невзвешенного графа, вы можете использоватьпоиск в ширину.

Если у вас естьn отn матрица:

for each vertex i:
    initialize an nxn matrix M
    run breadth-first search starting at i
    copy distances into row i of M
    return M
@ Hans напиши ответ, твой метод на самом деле правильный pyCthon
это займет вечность для большого дела pyCthon
@ Ханс: Флойд-Варшалл беретO(V^3) время в то время как BFS занимаетO(V^2+VE), BFS всегда быстрее, и значительно больше для разреженных графов. Самый быстрый способ найти кратчайший путь в неориентированном графе - это всегда BFS.
Вместо поиска в ширину, вероятно, было бы лучше использовать алгоритм дляall-pairs shortest-path problem
@tskuzzy: что V и E? Количество узлов / ребер? Здесь необходимы расстояния между всеми парами, насколько я понимаю, BFS находит только расстояние до корневого узла. Можете ли вы уточнить это? Кроме того, в реальной жизни константы действительно имеют значение ...

Похожие вопросы