用Tensorflow解决有向图问题

Question

我有一个看似简单的问题要用有向图来解决。给定一个有向图，例如图片中的那个，我需要找到两个“边界节点”(图片中的A和B )之间具有最小“最大成本”的路径。图中的每个节点都有一个要被入侵的“成本”，因此对于每个可能的路径，我们都可以找到最大的成本。例如，在图片中，路径3胜出，因为最大成本小于路径1和路径2的最大成本。

我总是听说Tensorflow是一个可以解决一般图形问题的库，所以我想知道Tensorflow周围是否有任何“随时可用”的库/后端可以让我解决这个问题？

谢谢你，拉斐尔

Example of directed graph

Answer 1

Tenserflow是一个机器学习框架，你不需要它来解决你想要解决的问题。您的问题可以通过简单地修改Dijkstra's algorithm来解决，如this问题中所述。唯一的区别是权重在节点上，而不是在边上，但您可以简单地构造一个新图，其中为每个原始边赋予权重为零，并将每个节点替换为两个新节点，一个用于传出边，另一个用于传入边。然后，还可以使用原始节点的权重将传入边节点的边添加到传出边节点。我让您验证这个新图中每个边的最小最大成本的路径对应于原始图中每个节点的最小最大成本的路径，并且您可以使用改进的Dijkstra算法找到该路径。