# Dijkstra's algorithm

• October 18th, 2012, 05:46 AM
dezett
Dijkstra's algorithm
Hello once again.
I wrote a program which uses Dijkstra's algorithm to give us the best weight path through an labyrinth (though every room has 2, 3 or 4 neighbours). Each room has it's weight. We simply create the labyrinth by command 'Graph graph = new Graph(n,m);'. Adding vertexes by 'graph.addVertex(position n, position m, weight);'. If you want to see a room and go through the labyrinth you must write 'graph.run(graph.vertexList[positon n][position m]);' - it should give the total weight of all visited rooms and the directions in which you should go. If you just want to go through you write: 'graph.Dijkstra(graph.vertexList[0][graph.n-1]);' since the entrance is always at [m][0] and the exit at [0][n]. To get the path in directions after command Dijkstra only 'graph.Path();'.
The problem is in the Graph.run command. It gives back good values for certain labyrinths, but for certain it does not. For example:
Code :

```Graph graph2 = new Graph(4,4); graph2.addVertex(0,0,1); graph2.addVertex(1,0,1); graph2.addVertex(2,0,1); graph2.addVertex(3,0,1); graph2.addVertex(0,1,1); graph2.addVertex(1,1,9); graph2.addVertex(2,1,9); graph2.addVertex(3,1,9); graph2.addVertex(0,2,1); graph2.addVertex(1,2,1); graph2.addVertex(2,2,9); graph2.addVertex(3,2,9); graph2.addVertex(0,3,1); graph2.addVertex(1,3,9); graph2.addVertex(2,3,9); graph2.addVertex(3,3,9);   graph2.run(graph2.vertexList[1][2]); graph2.run(graph2.vertexList[3][3]); graph2.Dijkstra(graph2.vertexList[0][graph2.n-1]); graph2.Path();```
Works and gives back good values while:

Code :

```Graph graph = new Graph(7,5); graph.addVertex(0,0,0); graph.addVertex(1,0,5); graph.addVertex(2,0,25); graph.addVertex(3,0,20); graph.addVertex(4,0,75); graph.addVertex(5,0,0); graph.addVertex(6,0,50); graph.addVertex(0,1,20); graph.addVertex(1,1,80); graph.addVertex(2,1,60); graph.addVertex(3,1,10); graph.addVertex(4,1,25); graph.addVertex(5,1,35); graph.addVertex(6,1,120); graph.addVertex(0,2,10); graph.addVertex(1,2,15); graph.addVertex(2,2,75); graph.addVertex(3,2,25); graph.addVertex(4,2,40); graph.addVertex(5,2,70); graph.addVertex(6,2,100); graph.addVertex(0,3,70); graph.addVertex(1,3,25); graph.addVertex(2,3,150); graph.addVertex(3,3,10); graph.addVertex(4,3,100); graph.addVertex(5,3,5); graph.addVertex(6,3,80); graph.addVertex(0,4,50); graph.addVertex(1,4,0); graph.addVertex(2,4,170); graph.addVertex(3,4,5); graph.addVertex(4,4,0); graph.addVertex(5,4,10); graph.addVertex(6,4,30);     graph.run(graph.vertexList[3][4]); graph.run(graph.vertexList[2][6]); graph.Dijkstra(graph.vertexList[0][graph.n-1]); graph.Path();```
crashes at the 1st graph.run. It says that u is null. Well, I simply agree since I was debugging it and saw that it goes to null. The thing is I just can't get to the point where the problem is. I just don't get why it doesn't work.
This is the whole project. It is written in NetBeans so I give you the whole folder with the classes. Attachment 1482

I'd reallly appreciate any help since my debugging can't do anything.
//EDIT: Don't know why but Dijkstra seems to stop before it gets to the final point. Think there must be something wrong with the method Dijkstra.
• October 18th, 2012, 09:50 AM
KevinWorkman
Re: Dijkstra's algorithm
You're going to have to boil your problem down to as small an example as you can: what kind of input causes your program to crash? Can you do it with fewer nodes?
• October 18th, 2012, 01:00 PM
dezett
Re: Dijkstra's algorithm
Well, I have found my mistake. The problem was in function Relax: I didn't add back the vertex which weight was the smallest of all. Thank you for your reply though.

//EDIT: Though now I have another problem. When putting a 5x5 labyrinth:
Code :

```Graph graph = new Graph(5,5); graph.addVertex(0,0,2); graph.addVertex(1,0,7); graph.addVertex(2,0,3); graph.addVertex(3,0,1); graph.addVertex(4,0,1); graph.addVertex(0,1,1); graph.addVertex(1,1,2); graph.addVertex(2,1,0); graph.addVertex(3,1,1); graph.addVertex(4,1,2); graph.addVertex(0,2,3); graph.addVertex(1,2,2); graph.addVertex(2,2,0); graph.addVertex(3,2,2); graph.addVertex(4,2,4); graph.addVertex(0,3,5); graph.addVertex(1,3,0); graph.addVertex(2,3,1); graph.addVertex(3,3,1); graph.addVertex(4,3,2); graph.addVertex(0,4,2); graph.addVertex(1,4,3); graph.addVertex(2,4,4); graph.addVertex(3,4,3); graph.addVertex(4,4,1);   graph.run(graph.vertexList[1][2]); graph.run(graph.vertexList[3][3]); graph.Dijkstra(graph.vertexList[0][graph.n-1]); graph.Path();```

it's just getting like element u.prev = v and v.prev = u till it's out of memory. Have no idea what statement should I make now to stop it.
• October 19th, 2012, 12:30 AM
jps
Re: Dijkstra's algorithm
Quote:

It says that u is null. Well, I simply agree since I was debugging it and saw that it goes to null. The thing is I just can't get to the point where the problem is. I just don't get why it doesn't work.
Where is the code with u ?

Please post relevant code on the forum rather than using an attachment. This is to make it more accessible to the readers.

Quote:

it's just getting like element u.prev = v and v.prev = u till it's out of memory.
Will need to see the code involved. If there is an error, paste the error message also.
• October 21st, 2012, 06:08 AM
dezett
Re: Dijkstra's algorithm
Ok, I will post the code and sorry for my absence from the topic but I had some problems.

So, this function gives the error:
Code :

```public void run(Vertex x) { this.roomNumber = 0; make0();   Dijkstra(x); int price = 0; List list = new List();   Vertex u = vertexList[m-1][0]; while(true) { price += u.weight; u.wasVisited = true; list.insert(u); // the error comes from this line if (u.equals(x)) break; u = u.prev; }   Dijkstra(vertexList[0][n-1]); //System.out.println(x.d + vertexList[0][n-1].weight);   while(true) { price += u.weight; u.wasVisited = true; list.insert(u); if (u.equals(vertexList[0][n-1])) break; u = u.prev; }   count(); System.out.print(price-x.weight + " " + this.roomNumber + " "); list.direction(); }```

//EDIT: The error:
Code :

```Exception in thread "main" java.lang.OutOfMemoryError: Java heap space at rynek.List.insert(List.java:17) at rynek.Graph.run(Graph.java:186) at rynek.Main.main(Main.java:360) Java Result: 1```

The methods which get involved in the error:

Code :

```public boolean Relax(Vertex u, Vertex v, Queue Q) { if(v.d >= u.d + v.weight) { //System.out.print(v.d + " " + "(" + v.i + "," + v.j + ")"); v.d = u.d + v.weight; v.prev = u;   Q.insert(v); // didn't had this line before and that was giving me the previous error return true; } return false; }   public void Dijkstra(Vertex s) { Init(); s.d = 0; // the best way (it's weight)   Queue Q = new Queue(n*m); for (int i=0; i<m; i++) { for (int j=0; j<n; j++) { Q.insert(vertexList[i][j]); } }   while(!Q.isEmpty()) { Vertex u = Q.deleteMin();   Element temp = u.list.first; while (temp != null) { Relax(u,temp.vertex, Q) temp = temp.next; } } }```
These 2 methods are used in the method "run". The "relax" function is making the u.prev = v and v.prev = u. I think I need some kind of statement to stop it, but just can't figure it out. I'm going to think it over but any help will be appreciated.
• October 21st, 2012, 03:32 PM
jps
Re: Dijkstra's algorithm
When does:
if (u.equals(x))
happen?

Is:
u = u.prev;
making changes to the value of u?

What do you see with a sysout on u.equals, x, u, and u.prev during a run?
• October 22nd, 2012, 07:08 AM
dezett
Re: Dijkstra's algorithm
u.equals(x) happens when 'u' gets through all the prevs to the room we wanted and needed to visit.

u = u.prev; is assigning the previous room to our variable 'u'.

'x' is a room we needed to visit while getting through the labyrinth. Is isn't changing.
'u' (in 'run') is a variable helping us to get all the rooms and weights of the best road in the 'list'.
'u.prev' is the best possible previous room considering weight.
'u.equals' gives false until it gets to the room 'x'.

Got another test which gives me an endless loop in the functions: Dijkstra and Relax. The thing is it is really tiny so maybe it'll help.
Code :

```3 3 0 0 0 0 4 4 0 1 1 3 3 2 2 1 2 2 1 0 0```

Room [0][0] -> prev [0][1]-> prev[0][0] and so on...

//EDIT: I have corrected the program, now it works well. The problem was in the Relax method. In the 1st if there must be if(v.d > u.d + v.weight) instead of if(v.d >= u.d + v.weight). Thanks for your replies.
• October 22nd, 2012, 04:53 PM
jps
Re: Dijkstra's algorithm