Итак, я пытаюсь закодировать алгоритм кратчайшего пути Дейкстры на С++. По какой-то причине он не правильно суммирует расстояния...
Вот что у меня есть для кода. Вы можете игнорировать раздел, в котором я копирую путь к стеку, потому что я знаю, что он еще не завершен. Есть идеи, где я ошибаюсь?
#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);
}