Эффективная оценка матрицы расстояний в библиотеке LEMON

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

Итак, рассмотрим нам дан большой граф (представлен в виде ListDigraph), подмножество вершин S и нам нужно оценить все кратчайшие пути между любыми двумя вершинами в S,

Самый простой способ сделать это - запустить Dijkstra алгоритм для каждой комбинации двух вершин в SНо, конечно, это не лучшая идея с точки зрения эффективности.

Одна вещь, которую я думал, состояла в том, чтобы оценить один путь от вершины i до вершины j, как в S, а затем найдите ProcessedMap для любой другой вершины в S. Если я найду одну, скажем, k, у меня уже есть расстояние от i до k. Это, скорее всего, уменьшит количество обращений к алгоритму. Однако я все еще думаю, что должно быть лучшее решение в лимоне.

Является ли добавление нескольких источников какой-либо помощи? Я еще не совсем понял поведение класса Dijkstra при использовании этой функции.

Спасибо =)

0 ответов

Другие вопросы по тегам