Results 1 to 1 of 1
 03202011, 02:17 AM #1Member
 Join Date
 Feb 2011
 Posts
 33
 Rep Power
 0
implementing an algorithm for shortest path problem in java
I am working on a project that has to do with finding the shortest path using from any tow vertices u,v. I have already written a code for most of this but I am having trouble figuring out the actual algorithm to cover all possible paths through the matrices and record all the values that end up at the very end.
So far I have
1. Set up variables so I can gain user input for ordered pairs
I accomplished this by setting up an array for x and an array for y.
2. Next I set up a way to connect x and y ordered pairs to each other to form your edges. I set this up using an array.
The code I have written so far is here:
Java Code:import java.util.Scanner; import java.math.*; public class Pathfinder { public static void main(String[] args) { int[] X = new int[100000]; int[] Y = new int[100000]; int[] rowcount = new int[100]; char[][] edge = new char['0']['0']; char[][] edge2 = new char['0']['0']; string[] pathtaken = [""]; int pathtakencount = 0; double distance[] = new double[1000.0000]; int nodenum = 1, nodenum2 = 0, nodenum3 = 0, loopcontinuer = 1, valuechecker = 0; int xsquared, ysquared, xdifference, ydifference; Scanner scan = new Scanner(System.in); System.out.println("please enter the value for the beginning node's X value:"); X[nodenum] = scan.nextInt(); System.out.println("please enter the value for the beginning node's Y value:"); Y[nodenum] = scan.nextInt(); while (loopcontinuer != 0) { nodenum++; System.out.println("please enter the value for node number " + nodenum + "'s X value"); X[nodenum] = scan.nextInt(); System.out.println("please enter the value for node number " + nodenum + "'s Y value"); Y[nodenum] = scan.nextInt(); System.out.println("would you like to enter another value? Enter \"0\" to end or any other number to continue."); System.out.println("Note by ending this sequence, the last term you entered becomes your destination"); loopcontinuer = scan.nextInt(); } for(nodenum2 = 0; nodenum2 < nodenum; nodenum2++) { nodenum3 = 1; while(nodenum3 < nodenum) { nodenum3++; System.out.println("Node" + nodenum3 + ":(" + X[nodenum3] + "," + Y[nodenum3] + ")"); } loopcontinuer = 1; while(loopcontinuer != 0) { System.out.println("Type in the nodes that node " + nodenum2 + " is connected to"); System.out.println("Please press enter between each input to connect them"); valuechecker = scan.nextInt(); if (valuechecker < 0  valuechecker > nodenum ) { System.out.println("Invalid input node entered not found!"); } else if(valuechecker == nodenum2) { System.out.println("loops are not allowed!"); } else { edge[nodenum2][valuechecker] = '1'; edge[valuechecker][nodenum2] = '1'; } System.out.println("Would you like to add another edge to node" + nodenum2 + "?"); System.out.println("Enter \"0\" if you do not, or any other number if you do"); loopcontinuer = scan.nextInt(); } } for(nodenum2 = 0; nodenum2 < nodenum; nodenum2++) { rowcount[nodenum2] = 0; for(nodenum3 = 0; nodenum3 < nodenum; nodenum3++) { edge2[nodenum2][nodenum3] = edge[nodenum2][nodenum3]; if(edge[nodenum2][nodenum3] = '1') { rowcount[nodenum2]++; } } while (rowcount[0] !=0) { nodenum2 = 0; while(edge2[0][nodenum2] != '1'  nodenum2 > nodenum) { nodenum2++; } if (edge2[0][nodenum2] == '1') { pathtaken[pathtakencount] = ("node: 0, node: " + nodenum2); xdistance = (x[0]  x[nodenum2]); ydistance = (y[0]  y[nodenum2]); xsquared = Math.pow(xdistance, 2); ysquared = Math.pow(ydistance, 2); distance[pathtakencount] = Math.sqrt((xsquared + ysquared)); edge2[0][nodenum2] == '0'; edge2[nodenum2][0] == '0'; } if (nodenum2 == nodenum) { pathtakencount++; } while (rowcount[nodenum2] > 0) { } } } } }
Similar Threads

Problem implementing ActionListener??
By ryanonnfire54 in forum New To JavaReplies: 3Last Post: 11162010, 05:39 PM 
Shortest SeekTime First with java.util.concurrent
By SAiNT_JiMMiE in forum Threads and SynchronizationReplies: 0Last Post: 05112010, 10:18 AM 
cannot resolve com.sun.java import  build path problem?
By chris97is in forum EclipseReplies: 6Last Post: 09112009, 12:34 AM 
problem with implementing list
By timkd127 in forum New To JavaReplies: 3Last Post: 04132009, 03:54 AM 
Help with a Graph Data Structure and the Shortest Path
By rhm54 in forum New To JavaReplies: 1Last Post: 03212008, 04:14 PM
Bookmarks