Dijkstra java algorithm description
I found an implementation of the dijkstras algorithm on the internet and was wondering if anyone could help me understand how the code works.
Many thanks
private int nr_points=0;
private int[][]Cost;
private int []mask;
private void dijkstraTSP()
{
if(nr_points==0)return;
//algorithm=new String("Dijkstra");
nod1=new Vector();
nod2=new Vector();
weight=new Vector();
mask=new int[nr_points];
//initialise mask with zeros (mask[x]=1 means the vertex is marked as used)
for(int i=0;i<nr_points;i++)mask[i]=0;
//Dijkstra:
int []dd=new int[nr_points];
int []pre=new int[nr_points];
int []path=new int[nr_points+1];
int init_vert=0,pos_in_path=0,new_vert=0;
//initialise the vectors
for(int i=0;i<nr_points;i++)
{
dd[i]=Cost[init_vert][i];
pre[i]=init_vert;
path[i]=-1;
}
pre[init_vert]=0;
path[0]=init_vert;
pos_in_path++;
mask[init_vert]=1;
for(int k=0;k<nr_points-1;k++)
{
//find min. cost in dd
for(int j=0;j<nr_points;j++)
if(dd[j]!=0 && mask[j]==0){new_vert=j; break;}
for(int j=0;j<nr_points;j++)
if(dd[j]<dd[new_vert] && mask[j]==0 && dd[j]!=0)new_vert=j;
mask[new_vert]=1;
path[pos_in_path]=new_vert;
pos_in_path++;
for(int j=0;j<nr_points;j++)
{
if(mask[j]==0)
{
if(dd[j]>dd[new_vert]+Cost[new_vert][j])
{
dd[j]=dd[new_vert]+Cost[new_vert][j];
}
}
}
}
//Close the cycle
path[nr_points]=init_vert;
//Save the solution in 3 vectors (for graphical purposes)
for(int i=0;i<nr_points;i++)
{
nod1.addElement(path[i]);
nod2.addElement(path[i+1]);
weight.addElement(Cost[path[i]][path[i+1]]);
}
}
a source to share
I think you need something like this: http://en.literateprograms.org/Dijkstra%27s_algorithm_%28Java%29
a source to share
I recently wrote Java code for this and documented how it works here: http://www.codescream.com/ContentDisplay?targetContent=DijkstrasAlgorithm
The excerpt below explains this in part; but you should look at the implementation plan in the link, not yours, as they will change.
Here Excerpt
-
Create a priority queue that always emit the node with the smallest distance from the source.
-
The queue stores all points that have not yet been visited. Add all vertices (points) to the queue; they all have an initial distance of Integer.MAX_VALUE.
-
Remove the origin from the queue explicitly and set its distance to 0 (this is zero from itself). Save this node as the "current" node. Repeatedly:
-
Calculate the distance from the current node to each neighbor.
-
If the distance from the current node to any neighbor is less than the adjacent current distance, update the adjacent distance value and set its "previous" node to the current node we're working from.
-
If we update the neighbor's values, we have to re-add it to the hidden points priority queue because its priority has changed. The lower distance makes the point more desirable in the queue.
-
After visiting all the neighbors, check if we are complete. We execute when the queue contains no more nodes (all nodes are visited) or when the best node in the queue (first) has a distance of infinity, since this means that it is not reachable from the starting point.
-
If the algorithm is not complete, select the next node from the top of the queue as the new "current" node and repeat. Being at the top of the queue, this node will be one of the shortest paths from the source in a way that makes it the best choice.
-
-
Once we broke this loop, we assigned a path to our nodes. So we start at the target node and follow the "previous" links to get back to the original one. The distance value at the target node is our "shortest path", and unmarking each node from the target to the source gives us the actual path.
-
Note that the path is reversed, so we push it onto the stack so that we can print it in reverse (i.e. forward from soruce).
a source to share
Instead of listing the steps of the algorithm (which often don't register well in our heads), I'll answer the big Why It Works questions that will be imprinted in your head from one read (hopefully).
It seems like a good explanation might be something that contains fewer words and speaks of the essential features of the algorithm. I will try to keep it short and build the simplest examples. Dijkstra's algorithm works because it selects the node with the minimum distance from an invisible set of nodes (not necessarily the nearest neighbors). Note that the distance at a node can be estimated, but it will only be visited after it has examined all of its neighbors (note how we already mentioned neighbors twice - so confusing!).
Now, to avoid confusion, just focus on the minimum and specified words. The word minimal is important so you don't break or clog the path. Let's consider an example:
1 1 1 1
src(0)->node1(Inf)->node2(Inf)->node3(Inf)->dot(Inf)
after the first step:
1 1 1 1
src(0)->node1(1)->node2(Inf)->node3(Inf)->dot(Inf)
Here, the top line shows the link lengths, and the second line shows the actual graph (the distance estimate is written in brackets). If, after updating node 1, we go to node 3 from the invisible set (breaking the minimum rule that node 2 suggests), we clog the graph. The clogged node will be fully handled (since it has visited all of its neighbors), but will have an Inf range estimate because it was updated too early. This way, updating the distance from the node with the minimum distance will ensure correct propagation. So a simple heuristic - Choose the best first (shortest calculated distance) to avoid cluttering the graph with suboptimal estimates.
Second, the word set is important because we cannot follow the min rule, which only searches for nearest neighbors. It may happen that the node with the minimum calculated distance is far from the current node.
node4(2)--node5(2)--node6(2)
/2 0 0 \
src(0) dst(2)
\1 1 2 /
node1(1)--node2(2)--node3(4)
As we follow the path, nodes 1, 2, and 3 accumulate distance 4, while nodes 5 and 6 will only have distance 2. So we have to abandon our nearest neighbors and jump to the node with the minimum distance (in our case, node 5). Hence, we say set, not neighbors; we are expanding our rule of Choose the best of the first, not even the neighbors. - and this is Dijkstra's algorithm in one non-professional sentence;)
a source to share