## Posts Tagged ‘dijkstras’

13Oct

So in my previous post a year ago. My graphing was actually based around small cases. Cases where verticies and edges could be represented as objects; however, in the real world this completely not optimal and does not work…

Dijkstra’s

** * This method performs a breadth first search. It will color all nodes, * list discovery times, and specify the discovery node. This can be used * information can then be accessed from the graph class. * @param startNode * The Vertex at which to start the search */ private void dijsktra(int sx, int sy, int ex, int ey){ int height = this.allNodes.length; int width = this.allNodes[0].length; nodes = new Node[height][width]; PriorityQueue<Node> q = new PriorityQueue<Node>(10000); q.offer(new Node(sx,sy,1,null,0,-1)); out: while(!q.isEmpty()){ Node u = q.poll(); for (int i=0; i<dy.length;i++){ int x = u.x+dx[i]; int y = u.y+dy[i]; if (x >= 0 && x < width && y >= 0 && y < height && allNodes[y][x] != 'x'){ Node a = new Node(x,y,1,u,u.weightFromStart+direction(i),i); if(Math.abs(a.weightFromStart-u.weightFromStart)>epsilon){ if (nodes[y][x]!=null && a.compareTo(nodes[y][x])==1){ q.remove(nodes[y][x]); nodes[y][x] = a; q.offer(a); } else if (nodes[y][x]==null){ nodes[y][x] = a; q.offer(a); } } } } } }

Breadth First:

char label may have been assignment specific. I don’t remember what it is for. I believe it is just the label I wanted to mark things with.

private static void bfs(int starti, int startj, char label){ int height = maze.length; int width = maze[0].length; //set color discovery[starti][startj][3]=1; //set discovery time discovery[starti][startj][2]=0; //create queue ArrayBlockingQueue<Integer[]> q = new ArrayBlockingQueue<Integer[]>(10000); Integer[] a = {starti,startj}; q.offer(a); while(!q.isEmpty()) { Integer[] u = q.poll(); for (int i=0;i<dx.length;i++){ if ((u[0]+dx[i]<height && u[1]+dy[i]<width)&&(((u[0]+dx[i]>=0 && u[1]+dy[i]>=0)&&(maze[u[0]+dx[i]][u[1]+dy[i]]!='x'&&maze[u[0]][u[1]]!='x'))&&discovery[u[0]+dx[i]][u[1]+dy[i]][3]==0)){ //color discovery[u[0]+dx[i]][u[1]+dy[i]][3] = 1; //disc time discovery[u[0]+dx[i]][u[1]+dy[i]][2] = discovery[u[0]][u[1]][2] + 1; //pi discovery[u[0]+dx[i]][u[1]+dy[i]][0] = u[0]; discovery[u[0]+dx[i]][u[1]+dy[i]][1] = u[1]; //update queue Integer[] b = {u[0]+dx[i],u[1]+dy[i]}; q.offer(b); } } discovery[u[0]][u[1]][3] = 2; if (maze[u[0]][u[1]]!='x') maze[u[0]][u[1]] = label; } }

Actually I don’t have depth first, but it is pretty similar. I am just you could figure it out :)!

Maybe I will include Kruskals and Prims sometime. I have those coded too. Hope this helps someone.