Алгоритм Дейкстры в C++

Question

Я должен реализовать алгоритм Дейкстры через ADT-граф, используя представление матрицы смежности для нахождения кратчайшего пути, улучшив псевдо-код ниже, используя либо язык 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

На проблемы я верю, ваша функция minDistance, кажется, что вы только обновить непосещенные узлы (строка 10, если (sptSet [v] == ложь & & расстояние [п] < = мин)). Наверное, это неправильно. Рассмотрим следующий график (узлы V = {n1, n2, n3, n4} со следующими расстояниями d (n1, n2) = 10; d (n1, n3) = 3; d (n3, n2) = 3 (все остальные являются бесконечность).

Начиная с n1 вы обнаружите, n2 со стоимостью 10

вы обнаружите также n3 со стоимостью 3

от п2 вы не делаете обнаружить короткий путь к п2 (n1-n3 -N2), так как вы отметили п2 уже как посещенные.

Я не уверен, если я райт. Если не DonT вините меня.

Answer 2

Наиболее очевидным несоответствием является то, что ваш код не имеет ничего, что соответствует массиву 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). Не то, чтобы это имело значение для стольких элементов, которые вы тестируете, конечно, но для больших графиков разница огромна.