Dijkstra.java

//http://algowiki.net

import javax.vecmath.Point3d;

public class Dijkstra {

	final int MAX;
	final int EDGES;
	final double INFINITE = 998.0;

	boolean allselected(int selected[])
	{
    		int i;
    		for (i=0;i<MAX;i++)
        	if (selected[i]==0)
            		return false;
    		return true;
	}

	void shortpath(double cost[][], int preced[], double distance[])
	{
		int selected[] = new int[MAX];
    		int current=0,i,k=0;
		double smalldist,newdist, dc;
    		for (i=0;i<MAX;i++)
        		distance[i]=INFINITE;
    		selected[current]=1;
    		distance[0]=0.0;
    		current=0;
    		while (!allselected(selected))
    		{
        		smalldist=INFINITE;
        		dc=distance[current];
        		for (i=0;i<MAX;i++)
        		{
            			if (selected[i]==0)
            			{
                			newdist=dc+cost[current][i];
                			if (newdist<distance[i])
                			{
                    				distance[i]=newdist;
                    				preced[i]=current;
                			}
                			if (distance[i]<smalldist)
                			{
                    				smalldist=distance[i];
                    				k=i;
                			}
            			}
        		}
        		current=k; // check if it's initialised
        		selected[current]=1;
    		}
	}

	void create_adj_matrix(Point3d points[], Edge edges[], double cost[][])
	{
	    int i, j;
	    for(i=0; i<MAX; i++)
		for(j=0; j<MAX; j++)
		    cost[i][j]  = INFINITE;
	    int e; 
	    for(e=0;e < sizeof(edges)/sizeof(edges[1]); e++)
		    edge = edges[e]
			edges[e] = points[edge.from].distance(points[edge.to])

	    //for each point we must calculate distance to other points.
            //we must make adjacency matrix from a set of points and a set of edges
            //your code here... Don't forget about point.distance(other_point)

            print_matrix(cost);
	}

	void print_matrix(double matrix[][])
	{
    		int i,j;
    		for(i=0;i<MAX;i++)
    		{
            		for(j=0; j<MAX; j++)
            		{
                		System.out.printf(" %f ", matrix[i][j]);
            		}
            		System.out.printf("\n\r");
    		}
    		System.out.printf("End of matrix\n\r");
	}


	public Dijkstra(int max, int edges)
	{
		MAX=max;
		EDGES=edges;
                System.out.println("Number of points: " + max + " Number of edges: " + edges);
	}

	int[] find(Point3d[] Nodes, Edge[] Edges)
	{
		double cost[][] = new double[MAX][MAX];
		create_adj_matrix(Nodes, Edges, cost);

		int i,preced[] = new int[MAX];
		double distance[] = new double[MAX];
		shortpath(cost,preced,distance);

                System.out.println("Distance:");
                for (i=0;i<MAX;i++)
                    System.out.println(distance[i]);
                System.out.println("Preced:");
                for (i=0;i<MAX;i++)
                    System.out.println(preced[i]);

		return preced;
	}
}