Dijkstra 算法中的 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)

如果您要寻找最短路径，为什么要使用称为 INT_MAX 的东西来计算称为 minDistance 的东西？你如何找到 INT_MAX？如果它完全影响答案，我正在使用 C++ 并且我的顶点是结构。但这是作业，所以没有答案的代码，请。

Answer 1

INT_MAX 是一个常量，表示 int 可以存储的最高可能值。它位于 "limits.h" http://www.cplusplus.com/reference/climits/

当你想找到某物的最短距离时，你想将当前评估的距离与你找到的最短距离进行比较"so far"，看看你是否找到了更短的距离。这通常涉及从最长可能的距离作为临时起点，这样您找到的任何距离都会自动变短。

如您所见，再往下，有一个语句 if (dist < minDistance)，它将始终是 true 第一个 时间，因为任何有效distance 有效保证小于最大可能距离值，INT_MAX.

许多类似的算法都使用相同的想法，在这些算法中，您想要找到最高或最低值：我们初始化为最差的可能值（根据上下文），以便接受找到的第一个有效值。

考虑一下如果我们不写 INT_MAX 而是其他一些较小的数字会发生什么。结果是您输入了一个相当于假值的值，该值将有效地与您正在测试的真实值竞争。因此，您始终希望保证初始 "fake" 值不会与任何实际值进行比较。

此外，如果在算法结束时找到的最短距离仍然等于 INT_MAX，那么您就知道 function/algorithm 根本没有找到有效距离。例如，函数可能只是 return minDistance，没有别的，然后调用者可以检查它是否等于 INT_MAX 来知道函数是否成功。（我并不是说这将是最好的设计。）

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

Dijkstra 算法中的 INT_MAX 是什么？

What is INT_MAX in Dijkstra's Algorithm?

c++

algorithm

dijkstra