c++ - 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;


}