Results 1 to 3 of 3
  1. #1
    Aliendox is offline Member
    Join Date
    Nov 2013
    Posts
    2
    Rep Power
    0

    Default MST (Kruskal) & Shortest Path (Djikstra)

    The shortest path method works fine on the initial graph, but it won't work on the MST.
    Anyone have any idea?
    If someone could just take a quick look at this and make sure that I'm not missing anything, that would be helpful. I'm only posting these two methods that are a part of my Graph class because I believe that it's the only relevant content. If you think you need more information, let me know.

    Java Code:
    public Path shortestPath(Vertex start, Vertex end){
    		Path p = new Path();
    		Vertex[] predecessor = new Vertex[activeVertices]; //creates array of vertices that will help keep track of what Vertex came before another
    		float[] distance = new float[activeVertices]; //distance away from the start Vertex
    		boolean[] inSet = new boolean[activeVertices]; 
    		final float infinity = Float.MAX_VALUE; //very large value for initial comparison
    		
    		for(int i = 0; i <activeVertices;i++){ //set all distances to infinity, predecessors to null, and false for inSet
    			distance[i] = infinity;
    			predecessor[i] = null;
    			inSet[i] = false;
    		}
    		distance[start.index]=0; //initialize start distance and mark it as in set
    		inSet[start.index]=true;
    		Vertex min = start; //min will keep track of the latest Vertex, and is therefore initialized as start
    		for(int m = 1; m<activeVertices; m++){ //iterate through all non-start Vertices
    			Iterator<Edge> i = min.edges.iterator(); //iterate through the edges of the min Vertex (iterate through neighbors)
    			while(i.hasNext()){
    				Edge e = i.next();
    				if(!inSet[e.destination.index] ){ //if the destination is not currently in the set...
    					if(distance[min.index]+e.distance < distance[e.destination.index]){ //...and the distance of the latest Vertex + the edge weight is less than the distance of the destination...
    						distance[e.destination.index]=distance[min.index]+e.distance; //then update the distance at the edge's destination
    						predecessor[e.destination.index]=min; //and store the latest Vertex as a predecessor of the destination
    					}
    				}
    			}
    			min=null; //reset min
    			for(int j = 0; j<activeVertices; j++){ //iterate through all vertices to find...
    				if(!inSet[j] && (min==null || (min!=null && distance[j]<distance[min.index]))){ //...the closest Vertex that is not in set 
    					min = vertices[j];
    				}
    			}
    			inSet[min.index] = true; //your new min needs to be added to the set
    		}
    		Vertex current = end; //starts the back track process to create the path by initializing a Vertex as the end airport
    		Iterator<Edge> i = vertices[current.index].edges.iterator(); //iterate through the edges of the end vertex
    		while(i.hasNext()){
    			Edge e = i.next();
    			if(e.destination == predecessor[current.index]){ //if the destination of the edge you find is equal to the predecessor of the current Vertex....
    															//you know that it's the right path because when the distance is updated at the edge's destination above...
    															//the latest Vertex is also stored as a predecessor.
    				p.path.add(new Edge(e.destination, current, e.distance)); //add a new edge to the path (in reverse order)
    				i = predecessor[current.index].edges.iterator(); //change the iterator so that it now iterates through the edges of the new Vertex (predecessor)
    				current = e.destination; //changes the current Vertex to the predecessor
    				p.hops++; //increments number of hops in the path
    				p.cost+=e.distance; //adds the weight to the total cost of the path
    			}
    		}
    		return p;
    	}
    	
    	public Graph minimumSpanningTree(){
    		Graph mst = new Graph(activeVertices);
    		PriorityQueue p = new PriorityQueue(activeVertices*activeVertices); //creates a new Priority queue of size n-squared because it's an undirected graph
    		int[] set = new int[activeVertices]; 
    		
    		for(int i = 0; i<activeVertices; i++){
    			mst.addVertex(vertices[i].name);
    			set[i] = i;
    		}
    		
    		for(int i = 0; i<activeVertices; i++){ //iterate through all vertices
    			Iterator<Edge> j = vertices[i].edges.iterator(); //iterate through all the edges of the current vertex
    			while(j.hasNext()){
    				p.enqueue(j.next()); //enqueue the edge into the priority queue
    			}
    		}
    		
    		while(!p.isEmpty()){
    			Edge e = p.dequeue();
    			if(set[e.source.index] != set[e.destination.index]){
    				mst.addEdge(e.source, e.destination, e.distance);
    				int merge = set[e.destination.index];
    				for(int i = 0; i<activeVertices; i++){
    					if(set[i]==merge){
    						set[i]=set[e.source.index];
    					}
    				}
    			}
    		}
    		return mst;
    	}

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,368
    Blog Entries
    7
    Rep Power
    20

    Default Re: MST (Kruskal) & Shortest Path (Djikstra)

    Quote Originally Posted by Aliendox View Post
    The shortest path method works fine on the initial graph, but it won't work on the MST.
    What does 'won't work' mean? Dijkstra's algorithm works on any graph without negative cost cycles; a MST is a tree, so there's only one path from any A to any B ...

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    Aliendox is offline Member
    Join Date
    Nov 2013
    Posts
    2
    Rep Power
    0

    Default Re: MST (Kruskal) & Shortest Path (Djikstra)

    Quote Originally Posted by JosAH View Post
    What does 'won't work' mean? Dijkstra's algorithm works on any graph without negative cost cycles; a MST is a tree, so there's only one path from any A to any B ...

    kind regards,

    Jos
    Meaning either there's something going on with the returned Graph from the MST method or for some reason my implementation of Djikstra doesn't work on MST.

Similar Threads

  1. Shortest path
    By csharp100 in forum New To Java
    Replies: 5
    Last Post: 03-23-2012, 10:25 AM
  2. Replies: 0
    Last Post: 03-20-2011, 01:17 AM
  3. Shortest Seek-Time First with java.util.concurrent
    By SAiNT_JiMMiE in forum Threads and Synchronization
    Replies: 0
    Last Post: 05-11-2010, 10:18 AM
  4. setting class-path & Library Path in ubantu
    By programmer_007 in forum Eclipse
    Replies: 18
    Last Post: 02-22-2010, 12:31 PM
  5. Replies: 1
    Last Post: 03-21-2008, 03:14 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •