Dijkstra 算法 C++

Question

我应该使用邻接矩阵和距离数组实现 Dijkstra 算法。这些是通过 class 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% 确定解决问题，因为您没有向我们展示 class 成员类型，也没有典型的失败示例。然而，一个困惑突然出现在眼前：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 !!

有符号和无符号之间的不匹配可能会导致您的比较出现意外结果（请参阅 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.

进行了比较

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

Dijkstra 算法 C++

Dijkstra's Algorithm c++

c++

algorithm

graph

dijkstra

初看：

解决方案