Dijkstra在C++中的算法

Question

我需要使用邻接矩阵表示通过ADT图实现Dijkstra算法,通过使用C/C++语言增强下面的伪代码来找到最短路径.

procedure Dijkstra(G, w, r, Parent[0:n-1], Dist)
  for v? 0 to n-1 do
    Dist[v] ? ?
    InTheTree[v] ? .false.
  endfor
  Parent[r] ?-1
  Dist[r] ?0
  for Stage ?1 to n-1 do 
    Select vertex u that minimises Dist[u] over all u such that InTheTree[u] = .false. 
    InTheTree[u] = .true.                                       // add u to T
    for each vertex v such that uv ? E do             // update Dist[v] and 
      if .not. InTheTree[v]  then                // Parent[v] arrays
        if Dist[u] + w(uv) < Dist[v]
          Dist[v] = Dist[u] + w(uv)
          Nearest[v] ?w(uv) 
          Parent[v] ? u
        endif
      endif
    endfor
  endfor
end Dijkstra

这是我用C++编码的代码解决方案.我的讲师声称代码不符合伪代码要求,我不确定它出错的地方,所以有人能帮我发现代码和伪代码之间的不匹配吗？

#include <stdio.h>
#include <limits.h>
#define N 9

int minDistance(int dist[], bool sptSet[])
{
   int min = INT_MAX, min_index;

   for (int n = 0; n < N; n++)
     if (sptSet[v] == false && dist[n] <= min)
         min = dist[n], min_index = n;

   return min_index;
}
int printSolution(int dist[], int v)
{
   printf("Vertex   Distance from Source\n");
   for (int i = 0; i < N; i++)
      printf("%d \t\t %d\n", i, dist[i]);
}
void dijkstra(int graph[N][N], int src)
{
     int dist[N];     

     bool sptSet[N];                         

     for (int i = 0; i < N; i++) {
        dist[i] = INT_MAX;
        sptSet[i] = false;
     }

     dist[src] = 0;


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

       int u = minDistance(dist, sptSet);
            sptSet[u] = true;
       for (int n = 0; n < N; n++)
         if (!sptSet[n] && graph[u][n] && dist[u] != INT_MAX 
                                       && dist[u]+graph[u][n] < dist[n])
            dist[n] = dist[u] + graph[u][n];
     }
     printSolution(dist, N);
}

int main()
{
   int graph[N][N] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
                      {4, 0, 8, 0, 0, 0, 0, 11, 0},
                      {0, 8, 0, 7, 0, 4, 0, 0, 2},
                      {0, 0, 7, 0, 9, 14, 0, 0, 0},
                      {0, 0, 0, 9, 0, 10, 0, 0, 0},
                      {0, 0, 4, 0, 10, 0, 2, 0, 0},
                      {0, 0, 0, 14, 0, 2, 0, 1, 6},
                      {8, 11, 0, 0, 0, 0, 1, 0, 7},
                      {0, 0, 2, 0, 0, 0, 6, 7, 0}
                     };

    dijkstra(graph, 0);

    return 0;
}

Answer 1

最明显的不匹配是您的代码没有与伪代码Parent数组相对应的任何内容.我把它作为输出参数,虽然它没有明确地标记.您似乎已经认识到,仅计算最小路径的长度不需要它,但它包含有关这些路径中实际步骤的所有信息,这通常是所需信息.

你也没有伪代码的模拟Nearest; 抱怨这一点有点意思,因为Nearest它不是例程的参数,并且伪代码没有显示其元素被读取.因此,它似乎没有任何有用的用途.

看来这段代码也不太匹配:

         if (!sptSet[n] && graph[u][n] && dist[u] != INT_MAX 
                                       && dist[u]+graph[u][n] < dist[n])
            dist[n] = dist[u] + graph[u][n];

该条件&& dist[u] != INT_MAX与伪代码中的任何内容都不对应.(这也是不必要的,因为u返回的是minDistance(),因此应始终满足该条件).

可以想象,您的教练也可能不满意您打印最小路径长度而不是返回它们.它取决于伪代码方言,但我倾向于Dist将参数列表中的外观作为输出参数的指示,而不仅仅是内部变量.

如果你的教练非常挑剔,那么也许你可以通过指出伪代码中的一些明显错误来获得一些松懈:

• 如前所述,Nearest它不是一个参数,而是写入但从未读取过.
• 看来条件if Dist[u] ? w(uv) < Dist[v] then应该是if Dist[u] + w(uv) < Dist[v] then.(您已经实现了正确的版本,这可以解释为与伪代码的另一个区别.)
• 它看起来Parent[r] ? u应该是Parent[v] ? u.

当然,可能是你的教练要求你准确地实现伪代码,错误和所有....

作为一个策略问题,我会尝试使用更好地匹配伪代码的变量名称.我不认为你的导师在这些理由上拒绝代码是不公平的,但是如果你跟你的名字更加接近,那么将C++代码与伪代码进行比较对每个人来说都会更容易.

虽然我正在讨论你的代码,顺便说一下,我观察到虽然你的minDistance()函数看起来实现了伪代码的要求,但它却以低效的方式实现(并且Dijkstra开始时并不是特别有效).通常的方法是使用最小堆来跟踪已经看到但尚未访问的节点,从而降低了从O(n)到O(log n)选择最小距离节点的成本.当然,并不是因为您正在测试的元素如此之少,但对于大型图形而言,差异是巨大的.

Answer 2

问题是我相信你的 minDistance 函数，似乎你只更新未访问的节点（第 10 行 if (sptSet[v] == false && dist[n] <= min)）。我想这是错误的。考虑下图（节点 V={n1, n2, n3, n4} ，其距离如下 d(n1, n2) = 10; d(n1,n3) = 3; d(n3,n2) = 3 （所有其他是无穷大）。

从 n1 开始，你发现 n2 的成本为 10

你还发现 n3 ，成本为 3

从 n2 你不会发现到 n2 的更短路径（n1-n3-n2），因为你已经将 n2 标记为已访问。

我不确定我是否正确。如果没有，别怪我。