ダイクストラのアルゴリズムでINT_MAXとは何ですか？

Question

私はDijkstraのアルゴリズムを実装しようとしていますが、基本的なレベルでそれを行う方法をかなり理解していますが、私を混乱させるものはINT_MAXです。ここで私は、次のよアルゴリズムです：あなたが最短経路を見つけようとしている場合

Dijkstra(start, end) 
    startV = search(start) 
    endV = search(end) 
    startV.solved = true 
    startV.distance = 0 
    solved = {startV} //list of solved vertices 
    while (!endV.solved) 
     minDistance = INT_MAX 
     solvedV = NULL 
     for s in solved 
      for y in s.adjacent 
       if(!y.solved) 
        dist = s.distance + y.distance 
        if(dist < minDistance) 
         solvedV = y 
         minDistance = dist 
         parent = s 
    solvedV.distance = minDistance 
    solvedV.parent = parent 
    solvedV.solved = true 

    solved.add(solvedV) 

はなぜminDistanceと呼ばれるものは、INT_MAXと呼ばれるものを使用して計算するのでしょうか？ INT_MAXはどうやって見つかりますか？それがまったく答えに影響するならば、私はC++を使っていますし、私の頂点は構造体です。しかし、それは宿題のためであり、答えのコードはありません。

Answer 1

INT_MAXは、intが保存できる最高可能値を表す定数です。 は、あなたが何かの最短距離を見つけたいとき、あなたは「これまでの」発見した最短距離で現在評価距離を比較して見たいと思って http://www.cplusplus.com/reference/climits/

「limits.hに」で発見されましたあなたが短いものを見つけたならば。 これは、通常、最長の可能な距離から開始し、一時的な出発点として、距離が自動的に短くなるようにします。

あなたがさらに下に、見ることができるように、任意の有効な距離が効果的に可能な最大距離値、INT_MAXより短くなることが保証されているので、常に、true最初時間になります声明、if (dist < minDistance)は、そこにあります。

同じ考え方が、最も高い値または最も低い値を見つける多くの同様のアルゴリズムで使用されています。最初に見つかった有効な値が受け入れられるように、最悪の可能な値（文脈上）で初期化されます。

私たちがINT_MAXと書くのではなく、他のいくつかの低い番号を書けばどうなるか考えてみましょう。その結果、偽の値に相当する金額が入力され、実際にの値と競合することになります。したがって、最初の「偽」値が実際の値との比較に失敗することが常に保証されることを常に望みます。

さらに、アルゴリズムの最後に見つかった最短距離がまだINT_MAXに等しい場合、関数/アルゴリズムが有効距離をまったく見つけられなかったことがわかります。たとえば、関数は単にminDistanceを返し、それ以外の場合は何も返しません。呼び出し元は、関数が成功したかどうかを知るためにINT_MAXに等しい場合にそれを確認できます。 （私はこれが最高のデザインであることを意味しているわけではありません）。

const int result(getMinDistance(whatever)); 
if (result == INT_MAX) // no real "minDistance" was actually found. 
else ... // found some real "minDistance" value.