的最短路径指数来，我被要求找出一种图形，其总的最短路径（使用Dijkstra算法）数量的节点（Dijkstra算法）

Question

的数数是指数的节点数量。 我想出了这样的曲线图：

A-> B-> C（与1重量每个边缘） A-> C（与重量2边缘）

C-> A' - > B'（所有边的权重= 1） B→B'（权重= 2）

B'→A“→B” B ''（重量= 2）

等等...

这种方式，最短轻拍的总数通过Dijkstra算法得到的这个图的hs是Ω（2 ^（n/2））。 我现在想弄清楚，如果它可以在东西一概而论类似Ω（2 ^（N/K）），其中k =每个节点的最短路径数。我也不知道，我怎么能够正确地证明解决方案的正确性。任何建议或提示非常感谢！ 我也希望你能指出我的解决方案中存在的任何缺陷。

在此先感谢！

Answer 1

你的解决方案是一个很好的起点。对于每添加几个节点，解决方案的数量可以增加一倍。但是，我不会立即看到每个节点如何拥有相同数量的最短路径。这可能会导致平均值较低，从而导致您的提案无效。

为了解决这个问题，你可以让你的图表2个稍作调整：使其周期性，并添加一些更多的联系。

使其具有周期性： 您应该将您的起始节点连接到最后一个节点。这将使图中的每个节点相等，因此它们都具有相同数量的最短路径。

添加一些链接： 在你的榜样，你给节点A链接到节点B和节点C的链接你也应该给B节点链接到节点C（已确定），并链接到节点A'。这相当于彼此。

为了证明是否正确，现在可以计算不同路径的数量为1个节点到所有其他节点，这对图中的所有节点有效的结果（这就是为什么他们应该是平等的）。为了证明指数性，可以看看如果向图中添加更多节点会发生什么情况，以及这会如何影响解决方案的数量。