Skip to content

Instantly share code, notes, and snippets.

Created June 4, 2013 05:22
Show Gist options
  • Save anonymous/5703772 to your computer and use it in GitHub Desktop.
Save anonymous/5703772 to your computer and use it in GitHub Desktop.
WOOOOOO Got my shortest path for graph workin
import graph.Vertex;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;
public class Main {
/**
* @param args
*/
public static void main(String[] args) throws FileNotFoundException
{
Scanner scn = new Scanner(new FileReader("vertex.txt"));//create new scanner to read .txt file
int numofvertices = scn.nextInt(); //find number of vertexes
int start = scn.nextInt();
int end = scn.nextInt();
ArrayList<Vertex> vertices = new ArrayList<Vertex>();
for(int i = 0; i < numofvertices;i++)
{
//make a new vertex for how many vertexes were called
vertices.add(new Vertex(i));
}
//load in matrix line
int node1 = scn.nextInt();
int node2 = scn.nextInt();
while (node1 != -1 && node2 != -1)
{
Vertex vertex1 = vertices.get(node1); //get vertex from node1
Vertex vertex2 = vertices.get(node2); //get vertex from node2
vertex1.adj.add(vertex2); //give node1's vertex directed adjacentcy to node 2
//load next matrix line
node1 = scn.nextInt();
node2 = scn.nextInt();
}
for (Vertex vertexOutput : vertices)
{
System.out.println(vertexOutput);
}
System.out.println();
//start destination queue
ArrayList<Vertex> vertexQue = new ArrayList<Vertex>(); //create a que of vertexs
vertices.get(start).isstartnode = true; //tell the start that it is the starting point
vertexQue.add(vertices.get(start)); //get start from original vertex list and place it in the que
while(!vertexQue.isEmpty())
{
Vertex parent = vertexQue.remove(0);
for(Vertex child : parent.adj)
{
if (!child.isstartnode == true)
{
child.isstartnode = true;
child.destination = parent;
vertexQue.add(child);
}
}
}
//start ordered traverse
Stack<Vertex> vertexStack = new Stack<Vertex>(); //create a new stack of vertexs
Vertex currentvertex = vertices.get(end); //select the end node
vertexStack.push(currentvertex); //add end node to the top of the stack
while(!vertexStack.peek().equals(vertices.get(start))) //while the stack hasnt reached the start node
{
currentvertex = currentvertex.destination; //the current vertex becomes the destination vertex
vertexStack.push(currentvertex); //push the current vertex onto the stack
}
while(!vertexStack.isEmpty()) //while the stack isnt empty
{
Vertex tempvertex = vertexStack.pop(); //take a vertex off the stack (starting with the start)
System.out.print(tempvertex.id); //print it out nicely in order
if(!vertexStack.isEmpty())
{
System.out.print("->");
}
}
System.out.println();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment