c++ - Dijkstra 算法 C++

Question

我应该使用邻接矩阵和距离数组来实现 Dijkstra 算法。这些是通过 Graph300 类实现的。该程序输入一个带有加权矩阵的文件，它正在进入矩阵。

为用户输出距离数组。但是我的 Dijkstras 不能正常工作。除了起始顶点(用户指定)之外，我一直为每个顶点获取 UINT_MAX :

Input matrix (4x4):
0           5           10           4294967295
4294967295  0           4294967295   3
4294967295  7           0            4294967295
4294967295  4294967295  4            0

My distance array should output:
distance[0]=4294967295 -nopath
distance[1]=0  -startnode
distance[2]=7
distance[3]=3

My output now (that is wrong):
distance[0]=4294967295 -nopath
distance[1]=0  -startnode
distance[2]=4294967295
distance[3]=4294967295

这是我的算法； numberNodes 是顶点的维度。 startNode 是用户指定的。矩阵数组和距离数组都是unsigned int类型:

void Graph300::dijkstra300()
{
    int startNode=getStartNode300();

    for (int i = 0; i < numberNodes; i++)
        distanceArray[i] = UINT_MAX;

    distanceArray[startNode] = 0;

    for (int count = 0; count < numberNodes-1; count++)
    {
         unsigned int min = INT_MAX, min_index;

         for (int v = 0; v < numberNodes; v++)
             if (visitedSet[v] == false && distanceArray[v] <= min)
                 min = distanceArray[v], min_index = v;

         int u = min_index;
         visitedSet[u] = true;

         for (int v = 0; v < numberNodes; v++)
             if (!visitedSet[v] && adjacencyMatrix[u][v] && distanceArray[u] != UINT_MAX
                && distanceArray[u]+adjacencyMatrix[u][v] < distanceArray[v])
                  distanceArray[v] = distanceArray[u] + adjacencyMatrix[u][v];
    }
    view300();  // display result
}

Answer 1

第一眼:

很难 100% 确定解决问题，因为您没有向我们展示类成员类型，也没有向我们展示失败的典型示例。然而，一个困惑突然出现在眼前:distanceArray[] 的类型是 unsigned int 还是 int ？

这里假设它是未签名的:

distanceArray[i] = UINT_MAX;   

但稍后您将此无符号整数与有符号整数进行比较:

int min = INT_MAX, min_index;   // min is signed integer !

for (int v = 0; v < numberNodes; v++)
   if (... && distanceArray[v] <= min)  // when comparing signed and unsigned you might not get the expected result !!

signed 和 unsigned 之间的不匹配可能会在您的比较中导致意想不到的结果(参见 online demo )。为避免此类问题，您要么只使用无符号值，要么将所有 UINT_MAX 更改为 INT_MAX。

解决方案

我可以找出您提供的附加数据的问题，并将所有距离切换为无符号整数。您必须更正您的if:

        if (!visitedSet[v] && adjacencyMatrix[u][v] && adjacencyMatrix[u][v] != UINT_MAX  
            && distanceArray[u] + adjacencyMatrix[u][v] < distanceArray[v])

因为您必须只考虑现有边 (adjacencyMatrix[u][v]!= UINT_MAX)。在您的代码中，您与 distanceArray 进行了比较。

我可以运行您的代码(在类之外)并根据您的输入获得预期的输出。这里是online demo .