Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 8 of 8

Thread: Dijkstra's algorithm

  1. #1
    Junior Member
    Join Date
    Jun 2012
    Posts
    18
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default 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:
    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.
    Last edited by dezett; October 18th, 2012 at 06:24 AM.


  2. #2
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,424
    My Mood
    Hungover
    Thanks
    144
    Thanked 636 Times in 540 Posts

    Default 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?
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  3. The Following User Says Thank You to KevinWorkman For This Useful Post:

    dezett (October 18th, 2012)

  4. #3
    Junior Member
    Join Date
    Jun 2012
    Posts
    18
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default 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:
    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.
    Last edited by dezett; October 21st, 2012 at 05:09 AM.

  5. #4
    Super Moderator jps's Avatar
    Join Date
    Jul 2012
    Posts
    2,642
    My Mood
    Daring
    Thanks
    90
    Thanked 263 Times in 232 Posts

    Default Re: Dijkstra's algorithm

    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.

  6. #5
    Junior Member
    Join Date
    Jun 2012
    Posts
    18
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default 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:
    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.
    Last edited by dezett; October 21st, 2012 at 07:34 AM. Reason: Giving additional info

  7. #6
    Super Moderator jps's Avatar
    Join Date
    Jul 2012
    Posts
    2,642
    My Mood
    Daring
    Thanks
    90
    Thanked 263 Times in 232 Posts

    Default 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?

  8. #7
    Junior Member
    Join Date
    Jun 2012
    Posts
    18
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default 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.
    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.
    Last edited by dezett; October 22nd, 2012 at 03:21 PM.

  9. #8
    Super Moderator jps's Avatar
    Join Date
    Jul 2012
    Posts
    2,642
    My Mood
    Daring
    Thanks
    90
    Thanked 263 Times in 232 Posts

    Default Re: Dijkstra's algorithm

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

Similar Threads

  1. Replies: 2
    Last Post: May 9th, 2012, 10:32 PM
  2. [SOLVED] Dijkstra's Algorithm
    By th3crack3n in forum Algorithms & Recursion
    Replies: 4
    Last Post: April 23rd, 2012, 06:18 PM
  3. Dijkstra's code help
    By csharp100 in forum What's Wrong With My Code?
    Replies: 18
    Last Post: March 24th, 2012, 08:15 PM
  4. MWM Algorithm
    By andreas90 in forum Algorithms & Recursion
    Replies: 5
    Last Post: January 11th, 2012, 03:43 AM
  5. all i need is algorithm
    By coder.freak in forum Paid Java Projects
    Replies: 3
    Last Post: April 6th, 2011, 11:11 AM