# MST (Kruskal) & Shortest Path (Djikstra)

• 11-25-2013, 03:44 AM
Aliendox
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.

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;         }```
• 11-25-2013, 10:49 AM
JosAH
Re: MST (Kruskal) & Shortest Path (Djikstra)
Quote:

Originally Posted by Aliendox
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
• 11-25-2013, 01:51 PM
Aliendox
Re: MST (Kruskal) & Shortest Path (Djikstra)
Quote:

Originally Posted by JosAH
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.