重建图以查找小于初始最短路径的优化图数
Reconstructing graph to find count of optimized graphs less than initial shortest path
我有一个带加权边（所有正整数）的图 G = {V,E} 并且我有这个图从源顶点 A 到目标顶点 B 的最短路径（可以说这个最短路径等于100) 使用 Dijkstra 算法找到。
我想找出用相同数量的边和节点重建此图的所有方法，但将节点之间的连接修改为绝对最短，直到我再次达到 100（旧的最短路径没有重建）
例如，我可以重构图，其中 A 连接到权重为 1 的 Z，因此我的最短路径为 1，这将是重构图的 1 种方式。另一种方法是 A 到 B 到 Z，每条边上的权重为 1，总路径的距离为 2。但是，我还想计算我们可以用权重为 2 的 A 到 Z 重建的路径。 ..99 最初，这仍然满足这条路径比第一条路径 (100) 短的条件
我正在尝试找出一种方法来找到所有可能的路径 "reconstructed" ，这些路径的距离小于初始图形的初始最短路径。
唯一的限制是我仍然必须使用第一个图中的所有顶点和边，但我可以将权重和边更改为使最短路径比以前更短的任何组合。
编辑：目标不是找到最短路径，而是可以用小于初始图从 A 到 Z 的最短路径的 A 到 Z 路径重建的图的最大数量。见评论下面进一步说明。
这听起来像是一个指数问题，因为您可以在源节点和目标节点之间任意添加任意数量的边，这是所有边都具有权重 (1) 的最简单情况。
为了便于讨论，让我们将问题简化为两组图，一组所有边的权重都为 1，另一组所有边的权重 "w" 为 2，用于目标加权路径"t" 共 100 个。
为了显示最坏的情况，让我们确保有足够的节点，因此对于任何给定的集合，我们将假设有大量的节点 "n" 可供选择，这样
n > t / w
因此第一组中使用的节点数具有 n > 100+1 的图形，对于第二组节点，该图形必须具有 n > 50+1，依此类推。
对于具有 100+1 个节点且边权重为 1 的图，您从节点 A 开始，然后可以选择任何剩余节点作为下一条边。从那里您重复选择下一个节点 98 次，然后您直接从当前节点直接连接到第 100 个边的节点 Z。由于在这种情况下我们不允许使用除 1 以外的循环或权重，因此我们完成了。这假设我们有有限数量的节点可供选择。对于边权重为 1 的图集，有 100 个阶乘（100！）答案满足您的标准。它变成了一个组合问题，尤其是当您的节点数超过目标路径长度（n = 200）时，它就变成了甚至更大，因为您可以从多组 100 个节点中进行选择以生成最终路径。
对于边权重为 2 的图，您执行相同的操作但需要更少的节点 (50+1)，但最终得到类似的结果 50!。现在对最大 100 的所有边权重（连接 A 和 Z 的单边）执行此操作，您将拥有所有路径的集合，这些路径具有统一的边权重，加起来等于您的目标长度。
因此，对于边权均匀且可被 100 整除的图集，最终图的最大数量为
100! + 50! + 25! + 20! + 10! + 5! + 4! + 2! + 1
从那里你仍然拥有所有权重不均匀的路径。但是您仍然可以从将非均匀权重组分解为子组开始。
当边权重不能被 100 整除时，您仍然可以得到一个值，例如边权重 3 将是 (33! + 1)，这意味着 33 条边的权重为 3，一条边为权重为 1，边权重为 6 得到 (16! + 4)，这意味着权重为 6 的 16 条边和权重为 4 的一条边。我们可以将这些称为双权重图。
组合学听起来是你当时最好的选择。
例如，您可以首先说有 n-1 种方法将 A 和 Z 与权重为 100 的单个节点连接起来。我不熟悉如何让它在 Whosebug 上正确显示，但您是说从一组 n-1 中选择 1。
然后你会发现所有的图都有一条权重为 99 的路径从 A 到某个任意节点 P，然后是另一条权重为 1 的边从 P 到目标节点 Z。所以第一条边可以从# 节点 - 2（不包括源节点和目标节点）然后第二条边是给定的，因为它必须连接到 Z。这给了我们
(n-2)! + 1
归结为 "choose 1 from a set of n-2 and then add 1"。一旦你过去了，它就会变得非常丑陋，因为开始有不止一种方法来选择剩余的边缘。
下一种情况是选择一个权重为98的单个节点，然后找到总权重为2的图集。
从具有 2 个节点的图开始并从那里向上开发通用方法可能更简单。
基本上，您必须同时从剩余边数和边权重中进行选择，以便为您提供可以连接的所有图的集合，给出给定值的路径长度。
我有一个带加权边（所有正整数）的图 G = {V,E} 并且我有这个图从源顶点 A 到目标顶点 B 的最短路径（可以说这个最短路径等于100) 使用 Dijkstra 算法找到。
我想找出用相同数量的边和节点重建此图的所有方法，但将节点之间的连接修改为绝对最短，直到我再次达到 100（旧的最短路径没有重建）
例如，我可以重构图，其中 A 连接到权重为 1 的 Z，因此我的最短路径为 1，这将是重构图的 1 种方式。另一种方法是 A 到 B 到 Z，每条边上的权重为 1，总路径的距离为 2。但是，我还想计算我们可以用权重为 2 的 A 到 Z 重建的路径。 ..99 最初，这仍然满足这条路径比第一条路径 (100) 短的条件
我正在尝试找出一种方法来找到所有可能的路径 "reconstructed" ，这些路径的距离小于初始图形的初始最短路径。
唯一的限制是我仍然必须使用第一个图中的所有顶点和边，但我可以将权重和边更改为使最短路径比以前更短的任何组合。
编辑：目标不是找到最短路径，而是可以用小于初始图从 A 到 Z 的最短路径的 A 到 Z 路径重建的图的最大数量。见评论下面进一步说明。
这听起来像是一个指数问题，因为您可以在源节点和目标节点之间任意添加任意数量的边，这是所有边都具有权重 (1) 的最简单情况。
为了便于讨论，让我们将问题简化为两组图，一组所有边的权重都为 1，另一组所有边的权重 "w" 为 2，用于目标加权路径"t" 共 100 个。
为了显示最坏的情况，让我们确保有足够的节点，因此对于任何给定的集合，我们将假设有大量的节点 "n" 可供选择，这样
n > t / w
因此第一组中使用的节点数具有 n > 100+1 的图形，对于第二组节点，该图形必须具有 n > 50+1，依此类推。
对于具有 100+1 个节点且边权重为 1 的图，您从节点 A 开始，然后可以选择任何剩余节点作为下一条边。从那里您重复选择下一个节点 98 次，然后您直接从当前节点直接连接到第 100 个边的节点 Z。由于在这种情况下我们不允许使用除 1 以外的循环或权重，因此我们完成了。这假设我们有有限数量的节点可供选择。对于边权重为 1 的图集，有 100 个阶乘（100！）答案满足您的标准。它变成了一个组合问题，尤其是当您的节点数超过目标路径长度（n = 200）时，它就变成了甚至更大，因为您可以从多组 100 个节点中进行选择以生成最终路径。
对于边权重为 2 的图，您执行相同的操作但需要更少的节点 (50+1)，但最终得到类似的结果 50!。现在对最大 100 的所有边权重（连接 A 和 Z 的单边）执行此操作，您将拥有所有路径的集合，这些路径具有统一的边权重，加起来等于您的目标长度。
因此，对于边权均匀且可被 100 整除的图集，最终图的最大数量为
100! + 50! + 25! + 20! + 10! + 5! + 4! + 2! + 1
从那里你仍然拥有所有权重不均匀的路径。但是您仍然可以从将非均匀权重组分解为子组开始。
当边权重不能被 100 整除时，您仍然可以得到一个值，例如边权重 3 将是 (33! + 1)，这意味着 33 条边的权重为 3，一条边为权重为 1，边权重为 6 得到 (16! + 4)，这意味着权重为 6 的 16 条边和权重为 4 的一条边。我们可以将这些称为双权重图。
组合学听起来是你当时最好的选择。
例如，您可以首先说有 n-1 种方法将 A 和 Z 与权重为 100 的单个节点连接起来。我不熟悉如何让它在 Whosebug 上正确显示，但您是说从一组 n-1 中选择 1。
然后你会发现所有的图都有一条权重为 99 的路径从 A 到某个任意节点 P，然后是另一条权重为 1 的边从 P 到目标节点 Z。所以第一条边可以从# 节点 - 2（不包括源节点和目标节点）然后第二条边是给定的，因为它必须连接到 Z。这给了我们
(n-2)! + 1
归结为 "choose 1 from a set of n-2 and then add 1"。一旦你过去了，它就会变得非常丑陋，因为开始有不止一种方法来选择剩余的边缘。
下一种情况是选择一个权重为98的单个节点，然后找到总权重为2的图集。
从具有 2 个节点的图开始并从那里向上开发通用方法可能更简单。
基本上，您必须同时从剩余边数和边权重中进行选择，以便为您提供可以连接的所有图的集合，给出给定值的路径长度。