python - 在加权图中找到下面定义的 "best"路径的任何好的算法？

Question

目前在学习图论，期间卡在了以下图相关的问题。让我们从一个例子开始。这听起来像是一道纯数学题。

例如:要实现的加权图:

上面显示了一个简化的图(它是从一个更复杂的网络中提取的)。

有5条简单路径，14条边及其各自的权值，11个节点(不同路径中的蓝色节点可以相同，但单条路径中的节点完全不同)。我试图找到节点 s 和节点 t 之间的最佳路径(均为黑色)满足以下条件:

1. 路径应尽可能短；
2. 路径上每条边的权重应尽可能大。

或者我什至可以根据某些方法对所有简单路径进行排名？

更具体地说，让我们将节点视为社交网络中的用户，将边每对用户之间的关联。权重与关联的可靠性成正比(10 是最可靠的，1 是最不可靠的)。

那么，有没有一种好的方法来定义和计算间接关联的权重(节点s和节点t 在例子中)？正如我们所知，一条路径在 s 和 t 之间的连接(边)越多，它的可靠性就越高趋于下降；而且，这条单一路径的每条连接的可靠性下降，也会导致其可靠性下降。这就是为什么上述条件需要更短的路径，以及路径的每条边上更大的权重。

谢谢你们的宝贵时间，伙计们!

Answer 1

由于该问题仅模糊地定义了每条可能路径的有利程度，因此该问题的答案应首先定义这样的排序。

根据您的问题定义，更具体地说，根据您关于社交网络关系的示例，我认为我们可以得出支持和反对一条路径有多有利的因素。

我们知道，在这种情况下，每条边都支持路径的可靠性，其数量与其成本或值(value)成正比。直觉上，似乎有一个因素支持路径的可靠性，它与路径上边的平均成本成正比。您还提到长度是影响事物的第二个因素，但这次是在另一个方向上。 (即反对路径的可靠性)

考虑到这两个因素，可以推导出如下公式，并用于对每条路径的可靠性进行排名。

如您所见，有一个求和表达式，其中 c_ei 表示每条边的成本 e_i 在路上。 n 表示路径上的边数。整个总和除以n本质上就是我上面提到的第一个因素。 (即路径上边的平均成本)而分母中表达式 n² 中的第二个 n 是第二个因素，即路径的长度，这与边的可靠性背道而驰。

我还介绍了 3 个常量，以便您可以根据您计划如何使用它来更新此公式。 C₂ 表示支持路径长度在降低整个路径可靠性方面的有效性的额外因素。类似地，C₁ 是一个因素，表明增加平均边成本在使该路径更可靠方面的效果如何。最后，C₃ 可以是一个可选因子，它可以等于路径上的最小或最大边成本。

虽然 C₁ 和 C₂ 相对更容易理解，但这里有一个 C₃ 可能派上用场的例子。假设您的路径 A 和 B 的边成本分别为 [3, 7, 8] 和 [5, 6, 7]。由于它们的路径长度和边成本之和相同，因此无法确定哪条路径更有利。这就是为什么在这种情况下我们需要一个因子，例如 C₃，并且根据您的需要，您可以认为它等于每条路径的最小边或最大边。如果您的问题定义选择前者并为 C₃ 分配每条路径的最小边成本，则路径 B 被认为更好，因为它的最小边成本更高。但是，如果选择后者，则路径 A 更为有利。

我知道，在我的答案中没有定义常量，在某种程度上，可能会让人觉得答案不完整。我相信下面给出的作业暂时应该有效。

C1 = 1C2 = 1C3 = min(cei)

不过，我相信这个问题的不同变体可能需要这些常量的不同值，这就是为什么我没有声明这些值适用于问题的所有变体。