Все кратчайшие пути, которые пересекают хотя бы один узел данной группы (ов) узлов

Question

В основном я хочу найти кратчайшие пути для всех (s, t) пар, но с несколькими соображениями. Например, сеть содержит несколько кластеров/сообществ или группу узлов. Эти группы будут предопределены и могут быть относительно большими в количестве узлов.

Я хочу найти кратчайшие пути для всех пар s, t, которые пересекают хотя бы один узел, например, из gourp1. В общем случае, если у меня есть только одна группа узлов, проблема сводится к традиционной взаимности между центрами. Позже я хотел бы найти для всех s, t пары кратчайшие пути, которые пересекают хотя бы один узел из gourp1 и group2.

Любые предложения?

Спасибо! :)

Answer 1

Согласно вашему описанию, мне кажется, что вы готовы получить кратчайшие пути для отдельной группы узлов. Если вы готовы это сделать, я думаю, вы направляетесь в правильном направлении.

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

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

Надеюсь, это поможет. :)