Как определить исходные и целевые параметры как массив для shorttest_path?

Question

Я использую NetworkX, opencv, numpy и python, чтобы найти shortest_path в графике. Это не всегда обеспечивает то, что мне нужно. Функция shorttest_path находит путь, начиная с верхней части изображения до нижней. Мой путь всегда меняется. Начальная точка и целевая точка всегда известны для каждого изображения. Таким образом, я хочу найти кратчайший путь между этими точками (начало и цель). Однако, когда исходная и целевая точки не являются узлами и не находятся в G, это не дает того, что мне нужно.

shortest_path(G, source=None, target=None, weight=None)

Как я могу найти shortest_path между двумя конкретными координатными точками на изображении? Кроме того, как я могу назначить пиксельные координаты как источник и цель? Например, источник [45 66] и цель [250 350]

Answer 1

Для второго выпуска у узла может быть сколько угодно измерений.
Например, рассмотрим следующую сетку.

import networkx as nx

g = nx.grid_2d_graph(2,2)

print(g.nodes()) #[(0, 0), (0, 1), (1, 0), (1, 1)]
print(g.edges()) #[((0, 0), (1, 0)), ((0, 0), (0, 1)), ((0, 1), (1, 1)), ((1, 0), (1, 1))]
print(nx.shortest_path(g, source=(0, 0), target=(1,0))) #[(0, 0), (1, 0)]

или с еще большим количеством размеров:

g = nx.grid_graph(dim=[2,2,2,2])
g.nodes()
#[(0, 0, 0, 0), (1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0), (0, 0, 0, 1), (1, 0, 0, 1), (0, 1, 0, 1), (0, 0, 1, 1), (1, 0, 1, 0), (0, 1, 1, 0), (1, 0, 1, 1), (0, 1, 1, 1), (1, 1, 0, 0), (1, 1, 0, 1), (1, 1, 1, 0), (1, 1, 1, 1)]

По остальным вопросам:

• Мой путь всегда меняется : это зависит от веса на краях, если кратчайший путь не уникален, это нормально, что он меняется

• , когда исходная и целевая точки не являются узлами и не находятся в G : networkx находит кратчайший путь между 2 узлами G, если узлы не находятся в G, это не будет работать