Thread: MST (Kruskal) & Shortest Path (Djikstra)

1. Member
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 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++){
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]){
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. Re: MST (Kruskal) & Shortest Path (Djikstra)

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

3. Member
Join Date
Nov 2013
Posts
2
Rep Power
0

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

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.

Posting Permissions

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