### Dijkstra's Algorithm producing incorrect results

In this implementation of Dijkstra I am trying to read a file in and apply the algorithm to it. While it does run, it does not produce the expected output. It will instead only evaluate the first case and no others. For example this file (the lone 0 is the starting point) produces the following output where 76543210 is my variant of infinity. What is the root of this problem?

File (node, destination, weight)
 ``1234567`` ``````0 0 1 2 0 2 4 1 2 1 1 3 5 2 4 3 3 4 1``````

Output
 ``12345678910`` ``````Enter the name of the file: a.txt The shortest distance from 0 to all the nodes is 0 : 76543212 1 : 76543210 2 : 76543210 3 : 76543210 4 : 76543210 5 : 76543210 ``````

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154`` ``````#include #include #include #include #include #include using namespace std; struct Edge { int end; //this is the node that the edge points to. int weight; //this is the weight of the node, very important! int origin; //finally, this is the node which we are pointing to, just in case it's needed. Edge(int start, int dest, int lbs): origin(start), end(dest), weight(lbs){ }; bool operator < (const Edge& a) const { return weight < a.weight; } }; const int INFINITY = 76543210; int filelength(string filename) { ifstream file; string str; int lines=0; file.open(filename); while (getline(file, str)) { lines++; } file.close(); return lines; } void dij(int x, const vector> &list, vector &path, vector &visited) { priority_queue Q; int a = list.size(); Edge origin = Edge(list[x][0].origin, list[x][0].end, list[x][0].weight); //origin.origin = x; path.clear(); //clean out any pre-existing junk path.resize(a, INFINITY); visited.resize(a, -1); Q.push(origin); path.clear(); path.assign(a, INFINITY); //cout<> list; vector path; vector visited; std::vector::size_type sz = path.size(); int e = 0; //This is the total size of the vector. It gets determined once string filename; printf("Enter the name of the file: "); cin>>filename; ifstream infile; infile.open(filename); int v = 0; int x; //cout<>x; Edge original(x, x, 0); original.origin = original.end; e = filelength(filename); list.resize(e); int a,b/*,c*/; //c=0; while(infile>>v>>a>>b) { list[v].push_back(Edge(v,a,b)); } //the first is the origin point, the second is the n-1th term. for example 00 is the first listed value of the node 0 //cout<>x; //quit(); return 0; } ``````
`for(std::size_t i=0;i < list[begin].size()-1;++i ) //line 60 ` ¿why -1?
 ``88899091`` `````` for(int i=0;i < list.size()-1;i++ ) //again ¿why -1? { cout << i << " : " << path[i] << endl; //you traverse path, but the condition is on list ¿? }``````

 ``70717273`` `````` if(path[i] < (path[begin] + list[begin][i].weight)) { path[i] = path[begin] + list[begin][i].weight; }``````
you've got it backwards. It should be If the new path is better, then change it.
Better is smaller
 ``12`` ``````if( path[begin]+list[begin][i].weight < path[i] ) path[i] = path[begin] + list[begin][i].weight;``````

Also, iirc std::priority_queue would make the top to be the greatest value, but you need the smaller here.

Another thing: `vector<int> &visited` if you want a collection of booleans, then use a collection of booleans `vector<bool> visited`
You initialize the elements to -1, anything that is not 0 is true. You say that all were already visited.

I don't see the point in asking it as a parameter either
Last edited on
Topic archived. No new replies allowed.