我被要求找出一种图，它的最短路径总数（使用 Dijkstra 算法）是节点数的指数。我想出了这样的图表：
A->B->C（每条边的权重为 1） A->C（边的权重为 2）
C->A'->B'（所有边的权重=1） C->B'（权重=2）
B'->A''->B''（所有边的权重=1） B'->B''（权重=2）
等等...
这样，Dijkstra 算法为该图找到的最短路径总数将为 Ω(2^(n/2))。我现在试图弄清楚它是否可以概括为 Ω(2^(n/k)) 之类的东西，其中 k = 每个节点的最短路径数。我也不知道如何正确证明解决方案的正确性。非常感谢任何建议或提示！如果您能指出我的解决方案中存在的任何缺陷，我也将不胜感激。
提前致谢！
您的解决方案是一个很好的起点。对于您添加的每几个节点，解决方案的数量可以增加一倍。但是，我并没有立即看到每个节点如何具有大约相同数量的最短路径。这可能会导致平均值较低，从而使您的提案无效。
要解决该问题，您可以对图表进行 2 项细微调整：使其具有周期性并添加更多链接。
使其具有循环性： 您应该将起始节点与最后一个节点连接起来。这将使图中的每个节点都相等，因此所有节点都具有相同数量的最短路径。
添加更多链接： 在您的示例中，您为节点 A 提供了到节点 B 的链接和到节点 C 的链接。您还应该为节点 B 提供到节点 C 的链接（已经可以）和到节点 A' 的链接。这等于彼此。
为了证明正确性，您现在可以计算 1 个节点到所有其他节点的不同路径的数量，这是图中所有节点的有效结果（这就是它们应该相等的原因）。为了证明指数性，您可以查看如果向图中添加更多节点会发生什么，以及这如何影响解决方案的数量。