Dijkstra 算法输出不正确

Question

我在实施 Dijkstra 算法时遇到问题。

我初始化了以下变量：

enum GraphLimit300 {MAX_NODES = 50};
typedef unsigned int Element300;
Element300 adjacencyMatrix[MAX_NODES][MAX_NODES];
Element300 distanceArray[MAX_NODES];
bool visitedSet[MAX_NODES];
int numberNodes;

这是我目前的算法实现：内部开始节点； int 访问过；

unsigned int smallest = UINT_MAX;
do
{
    startNode = getStartNode300();
    setVisitedSet300();
    smallest = UINT_MAX;
    visitedSet[startNode] = true;
    for (int i = 0; i < numberNodes; i++)
    {
        distanceArray[i] = adjacencyMatrix[startNode][i];
    }
    for (int i = 0; i < numberNodes - 1; i++)   
    {
        for (int v = 0; v < numberNodes; v++)
        {
            if (visitedSet[v] == false)
            {
                if (distanceArray[v] < smallest)
                {
                    smallest = distanceArray[v];
                    visited = v;
                }
            }
        }
        visitedSet[visited] = true;
        for (int w = 0; w < numberNodes; w++)
        {
            if (visitedSet[w] == false)
            {
                distanceArray[w] = min(distanceArray[w], distanceArray[visited] + adjacencyMatrix[visited][w]);
            }
        }
    }

在这个特定的 for 循环中，它应该执行特定的数学运算以找到节点为假的特定索引处的值之间的最小值，并将最小值存储在该索引中。我发现，在它选择 distaceArray 中的最小值并将其设置为 true 之后（如果我使用下面的数据文件从 1 开始，则为 3，这是正确的。）。

    for (int w = 0; w < numberNodes; w++)
        {
            if (visitedSet[w] == false)
            {
                distanceArray[w] = min(distanceArray[w], distanceArray[visited] + adjacencyMatrix[visited][w]);
            }
        }

它使用节点“0”和“2”，因为此特定迭代是错误的节点。并多次计算并将它们存储在错误的数组中。

我正在使用这个数据集来正确存储 adjacencyMatrix 中的数字。

0           5          10          4294967295
4294967295  0          4294967295  3
4294967295  7          0           4294967295
4294967295  4294967295 4           0

正确的输出是：

Distance[0] =4294967295
Distance[1] =0 //Which is the node that I choose to start with
Distance[2] =7
Distance[3] =3

我得到的是：

Distance[0] =3
Distance[1] =0
Distance[2] =3
Distance[3] =3

我已经手动完成了这个过程，以确认我应该得到的正确输出是真实的。

更新条件：

if (visitedSet[w] == false && adjacencyMatrix[visited][w] != UINT_MAX)
                {
                    distanceArray[w] = min(distanceArray[w], distanceArray[visited] + adjacencyMatrix[visited][w]);
                }

Answer 1

这里的问题又来了，你应该只考虑存在的边，即 adjacencyMatrix[visited][w]!=UINT_MAX。

如果您不排除这些边缘，distanceArray[visited] + adjacencyMatrix[visited][w] 将溢出并且 min() 不会 return 您期望的结果。

您可以通过更改此行来解决此问题：

if (visitedSet[w] == false && adjacencyMatrix[visited][w]!=UINT_MAX )

编辑：

您的嵌套for循环中确实隐藏了另一个问题。第一个内部 for 循环每次查找要展开的最短子路径。不幸的是，您没有重置 smallest，因此它从上一次迭代的最小值开始。

按如下方式更新循环，您将得到预期结果：

for (int i = 0; i < numberNodes - 1; i++)   
{
    smallest = UINT_MAX; // !!!!!!!!!!!!!!!!!!!!!!!
    for (int v = 0; v < numberNodes; v++) 
    {
        ...
    }
    ...
}

Dijkstra 算法输出不正确

Dijkstra Algorithm not outputting correctly

c++

algorithm

graph

dijkstra