Решить задачу ориентированного графа с Tensorflow

Question

У меня, казалось бы, простая задача, которую нужно решить в ориентированном графе. Учитывая направленный граф, такой как тот, что на рисунке, мне нужно найти путь между двумя «граничными узлами» (A и B, на рисунке), который имеет наименьшую «максимальную стоимость». Каждый узел в графе имеет определенную «стоимость» для вторжения, поэтому для каждого возможного пути мы можем найти максимальную стоимость. Например, на рисунке PATH 3 выигрывает, поскольку максимальная стоимость меньше, чем максимальная стоимость PATH 1 и PATH 2.

Я всегда слышал, что Tensorflow - это библиотека, которая позволяет вам решать общие проблемы с графами, поэтомуИнтересно, есть ли какая-нибудь "готовая к использованию" библиотека / бэкэнд вокруг Tensorflow, которая позволила бы мне решить эту проблему?

Спасибо, Рафаэль.

Пример направленногографик

Answer 1

Tenserflow - это система машинного обучения, которая не нужна для решения проблемы, которую вы хотите решить. Ваша проблема может быть решена простой модификацией алгоритма Дейкстры , как описано в этом вопросе. Единственное отличие состоит в том, что ваши веса находятся на узлах, а не на ребрах, но вы можете просто построить новый граф, в котором вы присваиваете каждому исходному ребру вес ноль и заменяете каждый узел двумя новыми узлами, один для исходящих ребер и один длявходящие ребра. Затем вы также добавляете ребро из узла входящего ребра в узел исходящего ребра с весом исходного узла. Я позволю вам убедиться, что путь минимальных максимальных затрат на ребро в этом новом графе соответствует пути минимальных максимальных затрат на узел в исходном графе, который вы можете найти с помощью модифицированного алгоритма Дейкстры.