1

頂点とエッジの両方について、リンクリストを使用してグラフを実装しましたが、これがダイクストラアルゴリズムの問​​題になりつつあります。前の質問で述べたように、隣接行列を使用するこのコードを変換して、グラフの実装を操作しています。

問題は、最小値を見つけると配列インデックスを取得することです。グラフの頂点が代わりに配列に格納されている場合、このインデックスは頂点インデックスと一致します。そして、頂点へのアクセスは一定になります。

グラフの実装を変更する時間はありませんが、一意の番号(ただし、0で始まらないもの、100090000のようなもの)でインデックス付けされたハッシュテーブルがあります。これが問題です。必要なときはいつでも、モジュロ演算子を使用して、0から頂点の総数までの数値を取得します。

これは、数値からの配列インデックスが必要な場合には問題なく機能しますが、配列インデックスからの数値が必要な場合(一定時間で計算された最小距離頂点にアクセスするため)、それほど多くはありません。

100090000 mod 18000=10000や10000invmod18000 = 100090000のように、モジュロ演算を逆にする方法を検索しようとしましたが、その方法が見つかりませんでした。

次の方法は、上記の例でarr [10000] = 100090000のような参照配列を作成することです。これで問題は解決しますが、グラフ全体をもう一度ループする必要があります。

現在のグラフの実装で、より良い/より簡単なソリューションはありますか?

4

1 に答える 1

1

配列には、カウント(またはそこに格納しているもの)を格納するだけでなく、カウントと頂点インデックス番号を含む構造を格納します。

于 2010-04-17T00:25:52.300 に答える