0

だから私はこれに何時間も取り組んできました、そして私は非常にイライラしています。何が間違っているのかわかりません。

ダイクストラのアルゴリズムを使用して、ソース頂点と隣接行列を使用する他の4つの頂点の間の最短経路を見つけています。この背後にある考え方は、5つの都市とそれらを行き来するフライトがあり、乗り継ぎを考慮して、最も安いチケット価格を見つける必要があるということです。

私は、擬似コードである私の本のアルゴリズムと、次のWebサイトのコードに従っています：http：//vinodcse.wordpress.com/2006/05/19/code-for-dijkstras-algorithm-in- c-2 /

私が抱えている問題は、Webサイトのネストされたforループで、カウンターiが1から始まることです。これが、ソース頂点からすべての頂点までの距離が正しい理由であると考えています。 999で変更されていません。

例：

現在の距離：999220 0115130

前任者：0 3 0 2 2

ソース頂点を変更した場合でも、変更されていない最初の距離を除いて、これらの距離はすべて正しいです。

カウンターiを0に変更すると、距離ごとに混乱します。

現在の距離：0 105 0 0 0

とにかく、助けてください。関連するコードは次のとおりです。

void Graph::findDistance(int startingVertex)
{
  for(int i=0; i<MAX;i++)
  {
    currentDistance[i] = 999;
    toBeChecked[i] = 1;
    predecessor[i] = 0; 
  }

  currentDistance[startingVertex]=0;
  bool flag=true;
  int v;
  while(flag)
  {
    v=minimum();

    toBeChecked[v]=0;

    for(int i=1; i<MAX;i++) //here is where i think im going wrong
    {
      if(adjecencyMatrix[v][i]>0)   
      {
        if(toBeChecked[i]!=0)
        {
          if(currentDistance[i] > currentDistance[v]+adjecencyMatrix[v][i][0].ticketPrice)
          {
            currentDistance[i] = currentDistance[v]+adjecencyMatrix[v][i][0].ticketPrice;
            predecessor[i]=v;
          }
        }
      }
    }

    flag = false;
    for(int i=1; i<MAX;i++)
    {
      if(toBeChecked[i]==1)
      flag=true;
    }
  }
}

int Graph::minimum()
{
  int min=999;
  int i,t;
  for(i=0;i<MAX;i++)
  {
    if(toBeChecked[i]!=0)
    {
      if(min>=currentDistance[i])
      {
        min=currentDistance[i];
        t=i;
      }
    }
  }
  return t;
}
4

1 に答える 1

1

これはチェックしないほうがいいですか

  if(adjecencyMatrix[v][i]>0)

adjecencyMatrix[v][i][0].ticketPrice残りの比較と同様に、で完了しますか？

が配列の場合adjecencyMatrix[v][i]、ポインターに変換され、そのポインターは常に 0 より大きくなります。配列からポインターへの減衰が再び発生します :)

于 2011-12-05T05:27:01.147 に答える