Блог

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

Учитывая два набора координат, сценарий, который я использую, ищет ближайшие узлы g , а затем вычисляет кратчайший путь между ними с помощью networkx nx.dijkstra_path . Изначально он был разработан для неориентированного графика, и сейчас я пытаюсь адаптировать его к более плотному ориентированному графику.

Следующий код выдает ошибку (скорее всего, из-за направленного характера g ):

 pos0, pos1 = (xo, yo)[::-1], (xd, yd)[::-1]
pos0_i = np.argmin(np.sum((LambNodes[:, ::-1] - pos0) ** 2, axis=1))
pos1_i = np.argmin(np.sum((LambNodes[:, ::-1] - pos1) ** 2, axis=1))

ilength, path = nx.dijkstra_path(roadgraph, source=tuple(LambNodes[pos0_i]), target=tuple(LambNodes[pos1_i]), weight=weight_name)  # minutes
 

 ValueError: ('Contradictory paths found:', 'negative weights?')
 

Я подумал о двух способах обойти эту проблему:

• 1) Первый-продолжать вычислять кратчайший путь до тех пор, пока не будет найден тот, который существует (например. «Если первых кратчайших путей не существует, попробуйте другой, а если и этого тоже не существует, продолжайте пробовать другие кратчайшие пути, пока не будет найден тот, который существует).
• 2) Второй-попытаться вычислить кратчайший путь, и если его не существует, то найдите второй ближайший узел к набору координат, заданному в начале, и повторите попытку.

Я не уверен, какой из них был бы наиболее актуальным. Есть какие-нибудь мысли по этому поводу?

Кроме того, я не уверен , как действовать 1) дальше, я попробовал метод, приведенный в документации nx:

 from itertools import islice

def k_shortest_paths(G, source, target, k, weight=weight_name):
    return list(
        islice(nx.shortest_simple_paths(G, source, target, weight=weight_name), k))
try:
    for path in k_shortest_paths(roadgraph, source, target, 5):
        print(path)
except ValueError:
    print('nope.')
 

Это не работает, так как большинство вычисленных кратчайших путей приводят к ошибке, и я не уверен, как это обойти.

Пожалуйста, дайте мне знать, если я недостаточно ясно описал свою проблему, и любая помощь будет очень признательна!