1

このスニペットが2つの頂点間の最短距離を見つける理由について簡単な説明はありますか?

for (k = 0; k < n; ++k)
  for (i = 0; i < n; ++i)
    for (j = 0; j < n; ++j)
      if (d[i][k] + d[k][j] < d[i][j])
        d[i][j] = d[i][k] + d[k][j]

そして、これはしません 

for (i = 0; i < n; ++i)
  for (j = 0; j < n; ++j)
    for (k = 0; k < n; ++k)
      if (d[i][k] + d[k][j] < d[i][j])
        d[i][j] = d[i][k] + d[k][j]

( k は 2 番目のスニペットの最も内側のものです)

4

4 に答える 4

4

kアイデアは、すべてのパスを改善するために、各ステップでノードを通過しようとすることで、パスを改善しようとするためi - jです。

表記法は問題ではありません。必要に応じてi, j, k代わりにループ変数として使用できますk, i, jが、上記のロジックを念頭に置いておく必要があります。その場合、各ステップを実行してj - kパスを改善する必要があります。i

for i = 0, n
  for j = 0, n
    for k = 0, n
      if d[j, i] + d[i, k] < d[j, k]
        d[j, k] = d[j, i] + d[i, k]

条件を変更せずに for ループの順序を変更することはできません。これは、別のアルゴリズムを取得するためです。それが何をするかは誰にもわかりません。

于 2013-01-26T22:03:40.747 に答える
2

の

for (k = 0; k < n; ++k)
  for (i = 0; i < n; ++i)
    for (j = 0; j < n; ++j)
      if (d[i][k] + d[k][j] < d[i][j])
        d[i][j] = d[i][k] + d[k][j]

最も外側のループは、とkの間のパス上にある頂点を参照しています。たとえば、次のように頂点を含む頂点間のすべてのパスを検討している場合ViVjk=1ViVjV1

Vi .... V1 .... Vj

さらに重要なことは、これらのパスの中から、リラクゼーションで最適なものを選択していることです。

if (d[i][k] + d[k][j] < d[i][j])
        d[i][j] = d[i][k] + d[k][j]

繰り返しますが、各反復は 2 つの頂点に焦点を当て、ViそれらVjの間の最適なパスを選択します。

失敗した他のインスタンスでは、2 つの固定された頂点間のパスの中で最適なものを選択していません。代わりに、2 つのセット頂点間のどのパスが最適かを見つけるのに十分な時間待っていませんVi。Vj

私がよく利用しているサイトである Geekviewpoint では、x andvを頂点としてt、また最も外側のループとして明確に使用しtています。（誰にとっても明らかではないので、彼らが実際に説明してくれたらよかったのに。）

//dynamically find the shortest distance between each pair.
    for (int t = 0; t < n; t++) {
      for (int v = 0; v < n; v++) {
        for (int u = 0; u < n; u++) {
          if (dist[v][u] > (long) dist[v][t] + dist[t][u]) {
            dist[v][u] = dist[v][t] + dist[t][u];
            pred[v][u] = pred[t][u];
          }
        }
      }
    }
于 2013-01-26T23:57:26.550 に答える
0

2 番目の欠陥のあるアルゴリズムの反例を見つけました。
i=0, j=1 の場合、仲介者を見つけようとしますが、何もありません。
次に、i=0、j=1 の仲介者が利用可能になると、再度チェックされることはなくなります。 ここに画像の説明を入力

于 2013-01-26T22:22:50.380 に答える