Я имею дело с очень большим (но разреженным) метрическим графом G, скажем, с N = 20000 вершинами, но не с множеством ребер, что позволяет хранить (используя scipy.sparse.matrix класс) соответствующую N x N весовую матрицу.
Мне будет интересна матрица кратчайшей длины пути (расстояние на графике), но я не могу сохранить матрицу расстояний N x N (которая больше не будет разреженной).Поэтому я выбрал небольшое количество k вершин, и мне было бы интересно вычислить k x k попарно кратчайшие расстояния между этими вершинами.
Функция scipy.sparse.csgraph.dijkstra (https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.sparse.csgraph.dijkstra.html)может быть адаптирован (с аргументом indices), но он вычисляет расстояния между точками до всех вершин графа - так что матрица k x N. Наряду с перерасходом во время выполнения, это также может привести к искажению памяти.
В принципе, было бы нормально вызвать функцию dijkstra(G, i, j), которая даст мне кратчайшую длину пути между вершинами i и j в графе G. Я знаю, что могу реализовать это самостоятельно, но я быЯ предпочитаю полагаться на его оптимизированную версию, и мне показалось бы безумным, что это не реализовано в какой-то стандартной библиотеке Python (numpy, scipy ...).
PS: Кроме того, если вы знаетеБиблиотека Python, которая использует знание того, что G является метрическим графом, и, например, например, кратчайший путь между двумя связанными вершинами - это весht соответствующего края и т. д. это было бы очень информативно: -)
PS2: обратите внимание, что мне не нужны кратчайшие пути.Только кратчайшая длина пути.
PS3: Чтобы исправить идею, эти графики построены из триангулированных трехмерных фигур.Вот почему это разреженные метрические графы.