The algorithm is described on-line fairly good, so I won't spend time describing it again here. The main ideas are that we need to keep a list with all the nodes that we visited and another list with all the nodes that we still haven't visited. At each iteration we take the unvisited node with the lowest distance from the source (calculated so far) and calculate the distance from the source to each of it's neighbors. We stop when there are no unvisited nodes.

I'm just going to print the algorithm since it does all the talking by itself. Some comments are available in the code which should explain everything.

` 1: #include <iostream>`

` 2: #include <vector>`

3: #include <string>

` 4: #include <set>`

` 5: #include <queue>`

6: using namespace std;

` 7: `

8: const int SIZE = 5; //number of nodes

9: int graph[SIZE][SIZE];//the graph itself

10: int d[SIZE]; //distances from the source to each node

11: int pi[SIZE];//contains the predecessor node for each node

12: vector<int> s;//list of nodes which were already visited

13: vector<int> vs;//list of nodes which were not visited yet

` 14: `

15: void sort(vector<int>* vec) {

16: //sorts the vector of nodes according to

17: //distances from the source to each node

18: for (unsigned int i = 0; i < vec->size(); i++)

19: for (unsigned int j = i; j < vec->size(); j++)

20: if (d[vec->at(i)] > d[vec->at(j)]) {

21: int temp = vec->at(i);

` 22: vec->at(i) = vec->at(j);`

` 23: vec->at(j) = temp;`

` 24: }`

` 25: }`

` 26: `

27: void relax(vector<int>* vec, int u) {

28: //updates the distances from the source to each node

29: //and the predecessor for each node

30: for (unsigned int i = 0; i < vec->size(); i++) {

31: int vi = vec->at(i);

32: if (graph[u][vi] == SHRT_MAX)

33: continue;

34: if (d[vi] > d[u] + graph[u][vi]) {

` 35: d[vi] = d[u] + graph[u][vi];`

` 36: pi[vi] = u;`

` 37: }`

` 38: }`

` 39: }`

` 40: `

41: void printShortestPathTo(int v) {

42: //this simply prints the vector of predecessors

43: //for the requested node (v)

44: cout << "Distance to " << v << " is " << d[v] << endl;

45: cout << "Shortest path: ";

46: int x = pi[v];

47: while (x != -1) {

48: cout << x << "<-";

` 49: x = pi[x];`

` 50: }`

` 51: cout << endl << endl;`

` 52: }`

` 53: `

54: int main() {

55: //initialize all the costs in the graph

56: for (int i = 0; i < SIZE; i++)

57: for (int j = 0; j < SIZE; j++)

` 58: graph[i][j] = SHRT_MAX;`

` 59: `

` 60: graph[0][1] = 20;`

` 61: graph[0][4] = 40;`

` 62: graph[1][4] = 50;`

` 63: graph[2][3] = 30;`

` 64: graph[2][4] = 60;`

` 65: graph[4][2] = 20;`

` 66: graph[4][3] = 100;`

` 67: `

68: for (int i = 0; i < SIZE; i++) {

69: for (int j = 0; j < SIZE; j++) {

70: cout << graph[i][j] << "\t";

` 71: }`

` 72: cout << endl;`

` 73: }`

74: for (int i = 0; i < SIZE; i++) {

75: vs.push_back(i);//initialize all the variables

76: d[i] = SHRT_MAX;//all distances to infinite

77: pi[i] = -1;//nodes have no predecesors

` 78: }`

79: d[0] = 0; //the distance of the source is 0

80: sort(&vs); //we sort the nodes according to the distance

` 81: `

82: while (vs.size() > 0) {

83: int x = vs.front();//take the node with the shortest distance

84: for (unsigned int i = 0; i < vs.size() - 1; i++) {

` 85: vs.at(i) = vs.at(i + 1);`

` 86: }`

` 87: vs.pop_back();`

88: s.push_back(x);//mark it as visited

89: relax(&vs, x);//update the distances

90: sort(&vs); //sort the nodes according to the new distances

` 91: }`

` 92: `

93: printShortestPathTo(4);//choose any node

94: return 0;

` 95: }`

Why have you included set and queue header files?

ReplyDeleteAre they needed at all?

They aren't needed. I have a kind of "template" with a bunch of stuff which I include in every new project (for me, it's sometimes faster because I can just edit the code without worrying that I didn't add the correct #include).

ReplyDeleteis that sorting function doing bubblesort?

ReplyDeleteyes. i'm quite ashamed of that now :)

ReplyDeletebut anyway, the point was to show an implementation of dijkstra... not optimal sorting

Argh !!!

ReplyDeleteYou're sorting the vs vector (with a poor algorithm) at each iteration of the loop ... That cost O(n^2)

Why not just looking for the min wich will be in O(n) ...

I simply followed the textbook algorithm, but that would be a nice improvement !! Thanks for your contribution.

ReplyDeleteAs for the sorting, standard STL sort could be used as well.

Like mentioned before, sorting all the rest nodes takes O(n^2), which is unnecessary.

ReplyDeleteWhy do not just just sorting only nodes that are successor of current nodes, that will be faster.

I would like to share following excellent applet for helping understanding:

http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html

Thanks.