преобразование матрицы смежности на расстояние или скачкообразный матрицы

Question

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

Answer 1

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

Предполагая, что у вас есть 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