Блог

Я использую cuGraph для вычисления кратчайшего пути графа, но вместо того, чтобы возвращать кратчайший путь к определенной вершине, он создает таблицу расстояний-вершин-предшественников:

 
        distance    vertex  predecessor
3935    0.000000    0       -1
3372    0.063761    1       173
3136    0.059330    2       236
395     0.096309    3       131
3780    0.078157    4       222
... ... ... ...
3886    0.157694    4886    4817
3062    0.226340    4887    4871
3895    0.171506    4888    4816
3057    0.165199    4889    4842
3898    0.213998    4890    4888
 

Как я могу получить путь к определенной вершине, используя этот график?

Я знаю, что могу просто перебирать его, пока не дойду до вершины 0, но это звучит неэффективно. Есть ли способ использовать векторизацию, чтобы сохранить ее эффективность?

в настоящее время единственный способ — передать возвращенные данные от цели обратно к источнику. Существует утилита под названием get_traversed_path(df, id), чтобы упростить это. Недавно мы объединили новый код CUDA, чтобы извлечь путь намного быстрее (cuGraph PR 1838) Мы работаем над добавлением оболочки python вокруг этого, и скоро у нас должна появиться новая функция