Dijkstra的最短路径算法问题

Question

所以我想在C++中编码Dijkstra的最短路径算法。由于某种原因，它没有正确地加上距离...

这是我到目前为止的代码。您可以忽略我将该路径复制到堆栈的部分，因为我知道它尚未完成。任何想法，我要去错了吗？

#include <fstream> 
#include "matrix.h" 
#include <list>  // STL container 
using namespace std; 
//--------------------------------------------------------------------------- 

const int INFIN = 100000; 
const int size = 8; 

double a[] = { 
     0, 0, 5, 0, 0, 2, 3, 0,  //length matrix (#9, page 276) 
     4, 0, 6, 0, 7, 0, 5, 0, 
     0, 3, 0, 9, 2, 6, 0, 7, 
     3, 0, 2, 0, 1, 0, 7, 6, 
     0, 5, 0, 1, 0, 0, 4, 0, 
     0, 0, 2, 0, 8, 0, 9, 0, 
     1, 2, 3, 0, 0, 6, 0, 0, 
     5, 0, 8, 0, 2, 0, 9, 0 
    }; 

     // Global declarations for L Matrix and begin and end node 

Matrix L(size,size,a);   //length matrix 
int begin, end; 

void path(long* D, int* P);  //function prototype for shortest path algorithm 

Matrix Warshall(Matrix M); 

void main() 
{ 
    int i, u; 
    long D [size+1];   //distance functions 
    int P [size+1];    //prior vertices in path 

    cout << "\nLength Matrix: " << L; 
    cout << "\nPaths that exist:" << Warshall(L); 

    for (i=1; i <= size; i++) { 
     D[i] = INFIN;   //initialize distance functions 
     P[i] = 0; 
} 


cout << "\nFind distance from vertex #"; 
cin >> begin; 
cout << "    to vertex #"; 
cin >> end; 

if (begin == end) exit(1); 
if (begin < 0 || end < 0) exit(1); 
if (begin > size || end > size) exit(1); 

path(D,P); 

cout << "\nShortest distance from \nvertex #" 
    << begin << " to vertex #" 
    << end << " is " << D[end]; 

// u = end; 
list<int> stack;   // work path backwards 
while (1) { 
    stack.push_front(end); 
    stack.push_front(begin); 
    break; 
    } 

    cout << "\nusing path:\n"; 
    cout << "\t" << stack.front(); 
    stack.pop_front(); 
    while (stack.size()) { 
     cout << " -> " << stack.front(); 
     stack.pop_front(); 
    } 
    getch(); 
} 

void path(long* D, int* P) { 
    int i, u, dist; 
    int U[size+1]; 
    for (i=1; i <= size; i++) 
    U[i] = 0; 
    U[begin] = 1;          // add first vertex; 
    D[begin] = 0; 
    u = begin; 
    do {       // until find end vertex 
     for (i = 1; i <= size; i++) { 
     dist = L.element(u,i);   // distance from u to i 
     if(D[u] + dist < D[i]) { 
      D[i] = D[u] + dist; 
      P[i] = u; 
      } 
    } 
     dist = 38000;   // reset distance value to large value 
     int min; 
     for(i = 1; i <= size; i++) { 
    if(L.element(u,i) != 0) { 
      if(L.element(u,i) < dist && U[i] != 1) { 
       dist = L.element(u,i); 
       min = i; 
      } 
     } 
    } 
    u = min; 
    U[u] = 1; 
    cout << "Min is " << min << endl; 
    } while (u != end); 
}    

Answer 1

if(D[u] + dist < D[i]) { 
      D[i] = D[u] + dist; 
      P[i] = u; 


} 

应该

if(D[u] + dist < D[i] && dist != 0) { 
      D[i] = D[u] + dist; 
      P[i] = u; 


}