Эффективная оценка матрицы расстояний в библиотеке LEMON
Я использую библиотеку LEMON в моем проекте, и у меня есть сомнения относительно того, как лучше всего использовать ее для оценки полной матрицы расстояний между вершинами в данном наборе.
Итак, рассмотрим нам дан большой граф (представлен в виде ListDigraph
), подмножество вершин S
и нам нужно оценить все кратчайшие пути между любыми двумя вершинами в S
,
Самый простой способ сделать это - запустить Dijkstra
алгоритм для каждой комбинации двух вершин в S
Но, конечно, это не лучшая идея с точки зрения эффективности.
Одна вещь, которую я думал, состояла в том, чтобы оценить один путь от вершины i до вершины j, как в S
, а затем найдите ProcessedMap
для любой другой вершины в S. Если я найду одну, скажем, k, у меня уже есть расстояние от i до k. Это, скорее всего, уменьшит количество обращений к алгоритму. Однако я все еще думаю, что должно быть лучшее решение в лимоне.
Является ли добавление нескольких источников какой-либо помощи? Я еще не совсем понял поведение класса Dijkstra
при использовании этой функции.
Спасибо =)