Вычислить кратчайшее расстояние от заданной вершины до вершины с заданным свойством

Question

Хорошо понимаемая проблема в теории графов - вычислить кратчайшее расстояние между двумя вершинами.

Что я хочу сделать, это найти кратчайшее расстояние от данной вершины до ближайшей вершины, которая имеет определенное значение свойства (точная вершина, которой это является, неизвестна).

Например, найдите кратчайшее расстояние от V(1) до ближайшей вершины V(?), где V(?).property(color)==red.

Подход, который я использовал для этого ранее, состоит в том, чтобы итеративно выйти из фокальной вершины, спрашивая у каждого невидимого соседа по пути, есть ли у него color=red.

Я также ограничил верхнее число шагов наружу для некоторой дополнительной эффективности, то есть ограничил поиск k ступенчатой ​​окрестностью .

1. Есть ли лучший способ решить эту проблему?
2. Как можно кодировать это, используя Gremlin ? (Я кодирую в основном на Python и не знаю, как перенести алгоритм через)

Answer 1

Как вы сказали, это хорошо известная проблема в теории графов, и есть много алгоритмов, таких как Дейкстра, которые решили эту проблему.вы можете прочитать о них здесь .

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

Изменяяусловие остановки цикла, я полагаю, оно даст вам желаемый результат:

g.V(1).repeat(out().simplePath()).until(has('color', 'red')).path().limit(1)