#python #graph #path #cluster-computing #similarity
Вопрос:
Мне нужно сделать следующее:
Учитывая полностью связный граф, я хочу вычислить сходство путей между каждой парой вершин.
Для этого для пары ($i$, $j$) необходимо взять максимальное значение набора минимального веса ребра для каждого пути, начинающегося с $i$ и заканчивающегося $j$.
Очевидно, что можно рассмотреть все пути между $i$ и $j$, взять минимальный вес ребра, а затем взять максимум между минимальными весами ребер, но это занимает слишком много времени для большого графика. Кто-нибудь знает способ сделать это быстрее?
Спасибо.
Комментарии:
1. Эта проблема не связана с программированием и может иметь больше смысла на другом сайте StackExchange (math.stackexchange.com, может быть?). Кроме того, в том виде, в каком он сформулирован сейчас (полностью связанный граф, минимальное ребро из всего пути), он всегда будет наименьшим ребром в графике.
2. Спасибо. Я искал, может быть, код, который мог бы это сделать. Возможно, моя формулировка немного запутана, но я хотел сказать следующее: в каждом пути берите значение минимального ребра, затем берите максимальное значение между всеми этими минимальными значениями. Итак, в резюме мне нужно вычислить список, который имеет значение минимального веса ребра для каждого пути, чем принимать максимальное значение этого списка. Ты знаешь какой-нибудь способ сделать это?
3. Опубликуйте образец графика и ожидаемый результат. Я попробую что-нибудь набросать
4. Марат, твое предложение задать мне задачу по математике.stackexchange было замечательным. Люди там обнаружили следующее: проблема с самым широким путем. Это то же самое, что и у меня, поэтому теперь я ограничиваю свой поиск в поисках хорошего алгоритма для решения этой проблемы.
5. Это может быть решено с помощью модификации Дейкстры. Единственное отличие заключается в том, что вместо увеличения расстояния по длине ребра вы берете минимальную ширину ребра и путь, ведущий к предыдущему узлу