# Dijkstra's Algorithm

• April 22nd, 2012, 10:10 PM
th3crack3n
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

Code :

```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++; } }   }```

Code :

```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); }```
• April 23rd, 2012, 06:12 AM
Norm
Re: Dijkstra's Algorithm
Quote:

i'm getting unsuspected errors
Please post the full text of the error messages.
• April 23rd, 2012, 09:28 AM
th3crack3n
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
• April 23rd, 2012, 09:46 AM
Norm
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.
• April 23rd, 2012, 06:18 PM
th3crack3n
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.