Dijkstra's Algorithm - Adjacency Lists

So I have been trying to implement the Dijkstra Algorithm for shortest path in a directed graph using adjacency lists, but for I don't know what reason, it doesn't print out the results (prints the minimum distance as 0 to all nodes).

The code I wrote is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <fstream>
#include <functional>
#include <climits>
#include <vector>
#include <queue>
#include <list>

using namespace std;

struct node {
	int vertex;
	int weight;
	node(int v, int w) : vertex(v), weight(w) { };
	node() { }
};

class CompareGreater {
	public:
		bool const operator()(node &nodeX, node &nodeY) {
			return (nodeX.weight > nodeY.weight) ;
		}
};

vector< list<node> > adj;
vector<int> weights;
priority_queue<node, vector<node>, CompareGreater> Q;

int nrVertices, nrEdges;

void readData();
void Dijkstra(node);
void writeData();

int main(int argc, char *argv[]) {

	readData();
	Dijkstra(node(1, 0));
	writeData();

	return 0;
}

void readData() {
	fstream in("dijkstra.in", ios::in);

	int nodeX, nodeY, weight;

	in >> nrVertices >> nrEdges;

	adj.resize(nrVertices+1);
	weights.resize(nrVertices+1);

	for (int i = 1; i <= nrVertices; ++i) {
		weights.push_back(INT_MAX);
	}

	for (int i = 1; i <= nrEdges; ++i) {
		in >> nodeX >> nodeY >> weight;
		adj[nodeX].push_back(node(nodeY, weight));
	}

	in.close();
}

void Dijkstra(node startNode) {
	node currentNode;

	weights[startNode.vertex] = 0;
	Q.push(startNode);

	while (!Q.empty()) {
		currentNode = Q.top();
		Q.pop();

		if (currentNode.weight <= weights[currentNode.vertex]) {
			for (list<node>::iterator it = adj[currentNode.vertex].begin(); it != adj[currentNode.vertex].end(); ++it) {
				if (weights[it->vertex] > weights[currentNode.vertex] + it->weight) {
					weights[it->vertex] = weights[currentNode.vertex] + it->weight;
					Q.push(node((it->vertex), weights[it->vertex]));
				}
			}
		}
	}
}

void writeData() {
	fstream out("dijkstra.out", ios::out);

	weights.resize(nrVertices+1);
	for (vector<int>::iterator it = weights.begin()+1; it != weights.end(); ++it) {
		out << (*it) << " ";
	}

	out.close();
}


The input data was:
5 7
1 2 10
1 3 2
1 5 100
2 4 3
3 2 5
4 3 15
4 5 5


It means there are 5 nodes, 7 arcs (directed edges), and the arcs exist from node 1 to 2 with the cost of 10, from 1 to 3 with the cost of 2, and so on.

However, the output is wrong. I have no idea where the program might fail. I took the main idea from here: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=standardTemplateLibrary2#dijkstra1
(At the end it gives the idea for Dijkstra's Algorithm using a priority_queue).

Thanks in advance.

Raul
Could anyone help me please? I need this solved before midnight.. :(

Raul
In readData you resize your weights vector, which, as well as increasing the capacity of the vector, also increases the number of elements in the vector. The elements so created are default constructed, which, in your case, means they take on the value of 0. So, the first nrVertices+1 elements of weights will be 0.

Then, you go on to increase the size of the weights vector further by appending the value of INT_MAX to the end of it, nrVertices times.

I suspect readData should look something like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void readData() {
    ifstream in("dijkstra.in");

    in >> nrVertices >> nrEdges;

    weights.swap(std::vector<int>(nrVertices + 1, INT_MAX));

    adj.resize(nrVertices + 1);
    for (int i = 1; i <= nrEdges; ++i) 
    {
        int nodeX, nodeY, weight;

        in >> nodeX >> nodeY >> weight;
        adj[nodeX].push_back(node(nodeY, weight));
    }
}
Last edited on
Yes, that's it, thank you very much sir. That was the problem. :)

Instead of weights.push_back(INT_MAX); I should have used weights.at(i) = INT_MAX;

Thanks again tho. Really appreciated.

Raul
Topic archived. No new replies allowed.