Dijkstra's algorithm

[dezett]

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:

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:

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. Rynek3.rar

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.

[KevinWorkman]

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?

[dezett]

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:

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.

[jps]

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.

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.

[dezett]

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:

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();
    }

The error itself I will add in a minute since I have to download NetBeans again.
//EDIT: The error:

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:

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.

[jps]

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?

[dezett]

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.

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.

[jps]

If your problem has been solved (happy dance for you) please mark the thread as solved.
Instructions can be found on the announcements page.