Przepisałem ten twój kod na wersję bardziej dla ludzi.
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int maxWeight = 100000;
struct DijkstraVertex{
int id;
int src;
int weight;
int toProcess;
DijkstraVertex(int i, int w=maxWeight):id(i),src(-1),weight(w),toProcess(true)
{}
};
vector<DijkstraVertex*> prepareVertices(int src, int size){
vector<DijkstraVertex*> vertices;
for(int i=0;i<size;i++){
if(i==src){
vertices.push_back(new DijkstraVertex(i,0));
}else{
vertices.push_back(new DijkstraVertex(i));
}
}
return vertices;
}
bool pathExists(const vector<int>& pathsFromVertex, int i) {
return pathsFromVertex[i] != 0;
}
int newCost(const vector<int>& pathsFromVertex, int i, DijkstraVertex* vertex) {
return vertex->weight + pathsFromVertex[i];
}
bool betterCostPath(const vector<DijkstraVertex*>& vertices, int i,
const vector<int>& pathsFromVertex, DijkstraVertex* vertex) {
return vertices[i]->weight > newCost(pathsFromVertex, i, vertex);
}
void relaxateVertex(DijkstraVertex* vertex, vector<vector<int> >& adiacenceMatrix, vector<DijkstraVertex*>& vertices){
vector<int> pathsFromVertex = adiacenceMatrix[vertex->id];
for(unsigned int i=0;i<pathsFromVertex.size();i++){
if (pathExists(pathsFromVertex, i) && betterCostPath(vertices, i, pathsFromVertex, vertex)) {
vertices[i]->weight = newCost(pathsFromVertex, i, vertex);
vertices[i]->src = vertex->id;
vertices[i]->toProcess = true;
}
}
}
vector<int> backtracePath(vector<DijkstraVertex*>& vertices, int src, int dst){
vector<int> path;
DijkstraVertex* vertex = vertices[dst];
path.push_back(dst);
while(vertex != vertices[src]){
path.push_back(vertex->src);
vertex = vertices[vertex->src];
}
return path;
}
DijkstraVertex* getMinVertex(vector<DijkstraVertex*> vertices){
int minWeight = maxWeight;
DijkstraVertex* minVertex = NULL;
for(unsigned i=0;i<vertices.size();i++){
DijkstraVertex* vertex = vertices[i];
if(vertex->toProcess && vertex->weight < minWeight){
minVertex = vertex;
minWeight = minVertex->weight;
}
}
minVertex->toProcess = false;
return minVertex;
}
vector<int> getPath(vector<vector<int> >& adiacenceMatrix, int src, int dst){
vector<DijkstraVertex*> vertices = prepareVertices(src, adiacenceMatrix.size());
while(true){
DijkstraVertex* vertex = getMinVertex(vertices);
if (vertex->id == dst){
break;
}
relaxateVertex(vertex, adiacenceMatrix, vertices);
}
return backtracePath(vertices, src, dst);
}
int main(){
vector<int> a;// = {0,1,3};
a.push_back(0);
a.push_back(1);
a.push_back(3);
vector<int> b;// = {1,0,1};
b.push_back(1);
b.push_back(0);
b.push_back(1);
vector<int> c;// = {3,1,0};
c.push_back(3);
c.push_back(1);
c.push_back(0);
vector<vector<int> > dane;// = {a,b,c};
dane.push_back(a);
dane.push_back(b);
dane.push_back(c);
vector<int> wynik = getPath(dane, 0, 2);
for(unsigned int i=0;i<wynik.size();i++){
cout<<wynik[i]<<" ";
}
return 0;
}