I'm implementing Dijkstra's algorithm for school and my code keeps messing up. I've followed the pseudo-code on Wikipedia very closely. I implement the graph with a weighted adjacency list in this form so I check neighbours by iterating through the corresponding row.
Here's my graph class, along with my vertex struct.
struct vertex
{
//constructor
vertex(size_t d_arg, size_t n_arg)
{
n = n_arg;
d = d_arg;
}
//member variables, n is name and d is distance
size_t n;
size_t d;
//overloaded operator so I can use std::sort in my priority queue
bool operator<(const vertex& rhs) const
{
return d<rhs.d;
}
};
class graph
{
public:
graph(vector<vector<size_t> > v){ ed = v;};
vector<size_t> dijkstra(size_t src);
bool dfs(size_t src);
private:
//stores my matrix describing the graph
vector<vector<size_t> > ed;
};
The function dfs implements a Depth-first Search to check if the graph's joint. I've got no problems with it. But the function dijkstra, however, gives me the wrong values. This is how it's implemented.
vector<size_t> graph::dijkstra(size_t src)
{
//a vector storing the distances to the vertices and a priority queue
vector<size_t> dist;
dist[src] = 0;
p_q<vertex> q;
//set the distance for the vertices to inphinity, since they're size_t and -1 is largest
for (size_t i = 0; i < ed.size(); i++) {
if(i!=src)
{
dist.push_back(-1);
}
//push the vertices to the priority queue
vertex node(dist[i], i);
q.push(node);
}
//while there's stuff in the queue
while(q.size())
{
//c, the current vertex, becomes the top
vertex c = q.pop();
//iterating through all the neighbours, listed in the adjacency matrix
for(int i = 0; i < ed[0].size(); i++)
{
//alternative distance to i is distance to current and distance between current and i
size_t alt = dist[c.n] + ed[c.n][i];
//if we've found a better distance
if(alt < dist[i])
{
//new distance is alternative distance, and it's pushed into the priority queue
dist[i] = alt;
vertex n(alt, i);
q.push(n);
}
}
}
return dist;
}
I can't see why I'm having trouble. I've debugged with this matrix.
0 3 -1 1
3 0 4 1
-1 4 0 -1
1 1 -1 0
And it didn't visit anything other than vertex 0 and vertex 3.