無向グラフの 2 つのノード間の最小距離を見つける必要があります。詳細は次のとおりです。
- グラフは無向で巨大です (ノード数は 100,000 のオーダーです)
- グラフはまばらです。エッジの数はノードの数よりも少なくなっています
- 私は実際のパスには興味がなく、距離だけに興味があります。
a) スペース効率 b) 時間効率のために、どの表現とアルゴリズムを使用すればよいですか?
編集：問題があれば、
- 重みはすべてゼロ以外の正の整数です。
- 自分自身に接続するノードはありません。
- 隣接する 2 つのノード間のエッジは 1 つだけ