我的问题是我想在图中的顶点 S 和 T 之间找到最短的 S(最可能的路径)，但我也有流约束，因为问题状态:
-你有一些 Ant (或其他什么)/一些房间/以及它们之间的一些链接，我必须一次让我的 Ant 转一圈，从 S 通过我的图表，到达 T , 但除 S 和 T 外，所有房间一次只能包含一只 Ant ，并且 Ant 可能不会在几个回合内被困在房间里。
所以我有一个流程图，所有边的容量都是一个(尊重每个房间里不超过一只 Ant )。
在这里我最终遇到了最大流量和最短路径之间的问题，因为两条路径之间可能存在一些捷径，有时如果我只有一只或少量 Ant ，那会更好只走一条路(走捷径)，把我的 Ant 排成一列，但是当 Ant 数量达到一定数量时，最好走两条路，不要走捷径，两只两只地送我的 Ant ，每条路一只，通过这样做，我将以最少的转弯结束我所有的 Ant 从 S 到 T。
到目前为止，我已经找到了一些最短路径的好算法，但它们总是给我错误的答案，因为它们可以找到阻塞流，这意味着采用一条最短路径而不是两条本来可以更好的路径，以避免这个问题我已经研究过最大流量问题，使用像 ford fulkerson 这样的算法，因为我可以跟踪阻塞流量并通过精确查看是否值得根据我的 Ant 反转捷径来反转它们，但是没有重量的概念，所以所有shortcut(这将被 max flow algo 逆转，因为 shortcuts 是唯一可能导致阻塞流的东西)，将是随机的，所以这很难证明，但我很确定那也是错误的，我认为这是一个比仅使用最短路径算法更好、更精确的方法，但我确信它在 100% 时再次不正确，特别是对于包含大量快捷方式的图形。
所以是的，这是学校作业，我不想让你做我的家庭作业，但我真的很想深入研究这个主题，而且我是所有图形方面的初学者，所以我'我对任何可以帮助我的算法感兴趣，或者任何可以帮助我的东西!
最佳答案
我认为您在寻找最大流量算法时走在了正确的道路上。您可以尝试以下三步法:
- 重建您的图表以合并您的(每个房间限制只有一只 Ant )。这可以通过用两个顶点 v_1、v_2 和容量为 1 的有向边 e(v_1, v_2) 替换每个房间顶点 v 来完成。所有进入 v 的边都连接到 v_1。 v 的所有出边都连接到 v_2。这样在任何时间点只有一只 Ant 可以通过 v(e(v_1, v_2))。两个房间之间的每条初始边的容量也为 1。
- 运行 Ford–Fulkerson algorithm 。这应该会告诉您使用哪些边缘来最大化流量。事实上，这应该为您提供从 S 到 T 的所有不同路径(没有两条路径共享一个房间)。
- 一旦您有了不同的路径，您就可以计算它们的长度，并据此可以直接计算出让所有 Ant 从 S 到 T 所需的步数。
关于algorithm - 通过最大流约束找到未加权图中的最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/51421230/