1

我一直在研究 Dijkstra 的算法很长一段时间，试图通过使用邻接矩阵来找出顶点之间的最短距离。似乎大多数算法都可以正常工作，但是当该移动到下一个顶点时我遇到了一些问题。这是我的代码：

/*Declarations and initialization*/
int* result;
int dist[this->nr_airport];
int unvisited[this->nr_airport];
int cur_vertex = source;
int check_dist = 0;
bool check_val_found = false;
for(int i=0 ; i<this->nr_airport ; i++)
{
     dist[i] = -1;      //-1 represents infinity
     unvisited[i] = i;  //the set of all unvisited nodes
}
dist[source] = 0;

/*Determining distances*/
for(int i=0 ; i<this->nr_airport ; i++)
{
    if(unvisited[i]!=-1 && this->matrix[cur_vertex][i]>0)   //Check if node is unvisited and neighbour to cur_vertex
    {
        if(dist[i]>=dist[cur_vertex]+this->matrix[cur_vertex][i] || dist[i]==-1)    //Check distance
        {
            dist[i] = dist[cur_vertex]+this->matrix[cur_vertex][i]; //Assign new distance
        }
    }
}

/*Setting the new vertex*/
for(int i=0 ; i<this->nr_airport ; i++)
{
    if(this->matrix[cur_vertex][i]>0 && unvisited[i]!=-1 && dist[i]>0)
    {
        if(!check_val_found)
        {
            check_dist = dist[i];
            cur_vertex = i;
            check_val_found = true;
        }
        if(dist[i]<check_dist)
        {
            check_dist = dist[i];
            cur_vertex = i;
        }
    }
}

首先，我循环遍历矩阵以确定当前顶点邻居的最短距离，并将该值分配给 dist[]。如果顶点未访问（未访问 []！=-1）并且矩阵值表明它是邻居，我会这样做。

然后，为了检查下一个顶点，我循环遍历所有顶点并检查它们与起始节点的距离，起始节点由 dist[] 保存。如果一个顶点已经被访问过 (unvisited[]==-1) 或者该顶点是当前顶点或不是当前顶点的邻居 (this->matrix[][]==0 或 this->matrix[] []==-1)，则它不会检查，因为该顶点不能是下一个要检查的顶点。

这里出了点问题，因为当我运行程序时，似乎首先，它没有检查它应该检查的所有顶点，其次，它检查了一些它不应该检查的顶点；我遇到的问题是我从一个顶点到另一个顶点，实际上它不是当前顶点的邻居。我检查了矩阵，它是正确的。

4

0 回答 0