迪杰斯特拉算法

Question

我有这个函数可以使用 Dijkstra 计算最短路径，但是代码在某些测试中给出了一些错误 cases.i 机器人可以在 code.Any 帮助中找出逻辑错误，我们将不胜感激。

 int minDistance(int *dist, bool *includ,int no_of_vertices);
int* shortestDist(int** graph, int src, int no_of_vertices)
{
     int u,a=no_of_vertices;
     int min = MAXval;int  min_index;
     int* dist= new int[no_of_vertices];     

     bool *includ = new bool[no_of_vertices]; 

     for (int i = 0; i < a ; i++)
       { dist[i] = MAXval;
        includ[i] = false;}


     dist[src] = 0;


     for (int count = 0; count < a-1; count++)
     {


      int u = minDistance(dist, includ,a);

       includ[u] = true;


       for (int v = 0; v < a; v++)


         if (!includ[v] && graph[u][v]  && ((dist[u]+graph[u][v]) < dist[v]))
            dist[v] = dist[u] + graph[u][v];

    }

     return dist;

}
int minDistance(int *dist, bool *includ,int no_of_vertices)
{            


   int min = MAXval;int min_index;

   for (int v = 0; v < no_of_vertices; v++)
   {
     if (includ[v] == false && dist[v] <= min)
         min = dist[v]; min_index = v;
 }
   return min_index;
}

测试用例：

预计o/p

0:5
1:1
2:0

实际o/p

0:1000
1:1
2:0

Answer 1

在minDistance(),

 if (includ[v] == false && dist[v] <= min)
     min = dist[v]; min_index = v;

你错过了 { }。 min_index = v;无论条件为真还是假都执行

迪杰斯特拉算法

Djikstra Algorithm

c++

algorithm

dijkstra

shortest-path

data-structures