Dijkstraの最短経路アルゴリズムの問​​題

Question

私はDijkstraの最短経路アルゴリズムをC++でコーディングしようとしています。何らかの理由で、正確に距離を加算していません...

これまでのコードではこれがあります。私はそれがまだ完全ではないことを知っているので、スタックへのパスをコピーしているセクションを無視することができます。私が間違っているアイデアは？

#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; 


}