Results 1 to 3 of 3
 11252013, 02:44 AM #1Member
 Join Date
 Nov 2013
 Posts
 2
 Rep Power
 0
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 nonstart 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 nsquared 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; }
 11252013, 09:49 AM #2
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,541
 Blog Entries
 7
 Rep Power
 20
Re: MST (Kruskal) & Shortest Path (Djikstra)
cenosillicaphobia: the fear for an empty beer glass
 11252013, 12:51 PM #3Member
 Join Date
 Nov 2013
 Posts
 2
 Rep Power
 0
Similar Threads

Shortest path
By csharp100 in forum New To JavaReplies: 5Last Post: 03232012, 10:25 AM 
implementing an algorithm for shortest path problem in java
By thorobred in forum New To JavaReplies: 0Last Post: 03202011, 01:17 AM 
Shortest SeekTime First with java.util.concurrent
By SAiNT_JiMMiE in forum Threads and SynchronizationReplies: 0Last Post: 05112010, 10:18 AM 
setting classpath & Library Path in ubantu
By programmer_007 in forum EclipseReplies: 18Last Post: 02222010, 12:31 PM 
Help with a Graph Data Structure and the Shortest Path
By rhm54 in forum New To JavaReplies: 1Last Post: 03212008, 03:14 PM
Bookmarks