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 5 of 5

Thread: Dijkstra's Algorithm

  1. #1
    Junior Member
    Join Date
    Apr 2012
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Dijkstra's Algorithm

    I am working on a project where I am attempting to find the central node, I think I heard it called a "Jordan node" of a graph network. I believe the best way to start this would be to run Dijkstra's algorithm and use the best possible path lengths (all weights = 1) to find the central node. But, as seen below, i'm getting unsuspected errors when I use a vertex that is not the first one entered. Some results show path lengths of zeros when that is not possible. Any help would be appreciated. I'm wondering if its an error with how 'dist' updates in the findDist(origin), but i'm not sure how to resolve it.

    The input file reads as follows:

    8 friends with 5
    4 friends with 8
    1 friends with 4
    1 friends with 5
    12 friends with 1
    11 friends with 12
    11 friends with 3
    11 friends with 6
    11 friends with 13
    11 friends with 7
    11 friends with 10
    11 friends with 2
    11 friends with 9
    12 friends with 3
    3 friends with 6
    6 friends with 13
    13 friends with 7
    7 friends with 10
    10 friends with 2
    2 friends with 9
    9 friends with 12

    Below are results I got using the first, second, and third vertex as start.


    Distance from : 8 to 8 : 0
    Distance from : 8 to 5 : 1
    Distance from : 8 to 4 : 1
    Distance from : 8 to 1 : 2
    Distance from : 8 to 12 : 3
    Distance from : 8 to 11 : 4
    Distance from : 8 to 3 : 4
    Distance from : 8 to 6 : 5
    Distance from : 8 to 13 : 5
    Distance from : 8 to 7 : 5
    Distance from : 8 to 10 : 5
    Distance from : 8 to 2 : 5
    Distance from : 8 to 9 : 4

    Distance from : 5 to 8 : 1
    Distance from : 5 to 5 : 2
    Distance from : 5 to 4 : 0
    Distance from : 5 to 1 : 1
    Distance from : 5 to 12 : 2
    Distance from : 5 to 11 : 3
    Distance from : 5 to 3 : 3
    Distance from : 5 to 6 : 4
    Distance from : 5 to 13 : 4
    Distance from : 5 to 7 : 4
    Distance from : 5 to 10 : 4
    Distance from : 5 to 2 : 4
    Distance from : 5 to 9 : 3

    Distance from : 4 to 8 : 1
    Distance from : 4 to 5 : 2
    Distance from : 4 to 4 : 0
    Distance from : 4 to 1 : 1
    Distance from : 4 to 12 : 2
    Distance from : 4 to 11 : 3
    Distance from : 4 to 3 : 3
    Distance from : 4 to 6 : 4
    Distance from : 4 to 13 : 4
    Distance from : 4 to 7 : 4
    Distance from : 4 to 10 : 4
    Distance from : 4 to 2 : 4
    Distance from : 4 to 9 : 3

    public static void findDist(Vertex origin){
    		origin.min = 0;
     
    		PriorityQueue<Vertex> vertexes = new PriorityQueue<Vertex>();
    		vertexes.add(origin);
     
    		while (!vertexes.isEmpty()) {
    			Vertex temp = vertexes.poll();
     
    			int n = 0;
    			while(temp.neighbors[n] != null) {
    				Vertex next = temp.neighbors[n].destination;
    				dist = temp.min + 1;
    				if (dist < next.min) {
    					vertexes.remove(next);
    					next.min = dist;
    					next.prev = temp;
    					vertexes.add(next);
    				}
    				n++;
    			}
    		}
     
    	}

    findDist(vertices[0]);
     
    		for (int w = 0; w < f; w++) {
    			System.out.println("Distance from : " + vertices[2].identifier + " to " + vertices[w].identifier + " : " + vertices[w].min);
    		}


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,199
    Thanks
    49
    Thanked 2,174 Times in 2,147 Posts

    Default Re: Dijkstra's Algorithm

    i'm getting unsuspected errors
    Please post the full text of the error messages.
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Junior Member
    Join Date
    Apr 2012
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Dijkstra's Algorithm

    By errors here I just mean errors in the distances I am getting back.

    Ex: In the second set of results, 5 to 5 is dist 2 and 5 to 4 is zero

  4. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,199
    Thanks
    49
    Thanked 2,174 Times in 2,147 Posts

    Default Re: Dijkstra's Algorithm

    Have you tried debugging the code by adding printlns to show the values of variables as they are changed while the code executes? If you know how the code is supposed to execute, the output will show you where the code is not doing what you want.
    If you don't understand my answer, don't ignore it, ask a question.

  5. #5
    Junior Member
    Join Date
    Apr 2012
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Dijkstra's Algorithm

    I actually figured it out as I was thinking through it at work today.

    It turns out that every time I called my algorithm, it edited the neighbors of each vertex.

    What I ended up doing to resolve the issue was to pull the graph creation to a separate method, and call it at the end of each run of the algorithm. This set the graph back to it's original state.

Similar Threads

  1. Dijkstra's code help
    By csharp100 in forum What's Wrong With My Code?
    Replies: 18
    Last Post: March 24th, 2012, 08:15 PM
  2. MWM Algorithm
    By andreas90 in forum Algorithms & Recursion
    Replies: 5
    Last Post: January 11th, 2012, 02:43 AM
  3. CRC algorithm
    By aldykid in forum Algorithms & Recursion
    Replies: 1
    Last Post: August 7th, 2011, 10:50 AM
  4. all i need is algorithm
    By coder.freak in forum Paid Java Projects
    Replies: 3
    Last Post: April 6th, 2011, 11:11 AM
  5. [SOLVED] Algorithm Help
    By aussiemcgr in forum Java Theory & Questions
    Replies: 2
    Last Post: September 10th, 2010, 04:12 PM