最短経路の総数が (ダイクストラのアルゴリズムを使用して) ノード数に対して指数関数的である一種のグラフを見つけ出すように依頼されました。私はそのようなグラフを思いついた：
A->B->C (重み 1 の各エッジ) A->C (重み 2 のエッジ)
C->A'->B' (すべてのエッジの重み = 1) C->B' (重み = 2)
B'->A''->B'' (すべてのエッジの重み = 1) B'->B'' (重み = 2)
等々...
このように、このグラフのダイクストラのアルゴリズムによって検出された最短経路の総数は Ω(2^(n/2)) になります。Ω(2^(n/k)) のようなもので一般化できるかどうかを把握しようとしています。ここで、k = ノードあたりの最短パスの数です。また、解決策の正しさを適切に証明する方法もまだわかりません。アドバイスやヒントは大歓迎です！また、私のソリューションの既存の欠陥を指摘していただければ幸いです。
前もって感謝します！
あなたのソリューションは良い出発点です。いくつかのノードを追加するたびに、ソリューションの数を 2 倍にすることができます。ただし、すべてのノードがほぼ同じ量の最短パスを持つ方法はすぐにはわかりません。これにより、平均が低くなり、提案が無効になる可能性があります。
この問題を解決するには、グラフに 2 つのわずかな調整を加えることができます。グラフを周期的にし、さらにリンクを追加します。
周期的にする: 開始ノードを最後のノードに接続する必要があります。これにより、グラフ内のすべてのノードが等しくなり、すべてのノードが同じ数の最短経路を持ちます。
さらにいくつかのリンクを追加します: あなたの例では、ノード A にノード B へのリンクとノード C へのリンクを与えます。また、ノード B にノード C (すでに OK) へのリンクとノード A' へのリンクを与える必要があります。これは互いに等しい。
正確さを証明するために、1 つのノードから他のすべてのノードへの個別のパスの数を計算できるようになりました。これは、グラフ内のすべてのノードに対して有効な結果です (これが、それらが等しい必要がある理由です)。指数関数性を証明するために、グラフにノードを追加するとどうなるか、それが解の数にどのように影響するかを調べることができます。