Можно ли преобразовать матрицу смежности из единиц и нулей, как определено здесь в матрицу расстояний, как определено здесь, где каждая ссылка будет иметь единичную длину 1?
Преобразование матрицы смежности в матрицу расстояний или прыжков
comment
У вас есть информация о весе каждой ссылки?
- person Manlio schedule 10.04.2012
comment
да я отредактировал вопрос
- person pyCthon schedule 10.04.2012
Ответы (1)
Матрица смежности единиц и нулей — это просто представление неориентированного графа. Чтобы получить расстояния между любыми двумя вершинами невзвешенного графа, вы можете использовать поиск в ширину. .
Предполагая, что у вас есть матрица 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
person
tskuzzy
schedule
09.04.2012
Вместо поиска в ширину, вероятно, было бы лучше использовать алгоритм для задачи поиска кратчайшего пути для всех пар
- person Hans; 10.04.2012
это займет вечность для большого дела
- person pyCthon; 10.04.2012
@Hans: Floyd-Warshall занимает
O(V^3) время, тогда как BFS занимает O(V^2+VE). BFS всегда быстрее и значительно быстрее для разреженных графов. Самый быстрый способ найти кратчайший путь в неориентированном графе — это всегда BFS.
- person tskuzzy; 10.04.2012
@tskuzzy: что такое В и Е? Количество узлов/ребер? Здесь нужны расстояния между всеми парами, насколько я понимаю, BFS находит только расстояние до корневого узла - можно поподробнее? Кроме того, в реальной жизни константы действительно имеют значение...
- person Hans; 11.04.2012
@Hans: Да, V — это количество вершин, а E — количество ребер. Мы запускаем BFS для каждой вершины, чтобы вычислить кратчайший путь для всех пар. Константы, связанные с BFS, сравнимы с константами FW, если не меньше. Если вы сравните их, вы увидите, что BFS лучше.
- person tskuzzy; 11.04.2012
оба хороших момента мне пришлось использовать алгоритм Дейкстры с кучами Фибоначчи из реализации, которую я нашел в Интернете
- person pyCthon; 15.04.2012
