-
Breadth first search with java
I have some problems building my breadth first search algorithm with java, hope u guys can help me..
BFS basically is used to search a graph by dividing the graph into levels and searching a node, and its neighbour and its neighbour's neighbour (hope i'm correct with d concept)
However, in my case i have to solve a travelling salesman problem where i have a distance table of 10 cities, A to J
Code:
public static DistanceTable getDefault(){
String[] legends = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J"};
double[][] distance = {{0.0},
{1.3, 0.0},
{2.5, 5.8, 0.0},
{3.6, 4.3, 6.3, 0.0},
{4.2, 8.9, 4.5, 7.1, 0.0},
{5.9, 6.7, 8.1, 8.6, 7.6, 0.0},
{6.7, 5.4, 7.8, 6.4, 2.4, 4.8, 0.0},
{7.1, 2.6, 1.6, 2.1, 3.6, 6.3, 7.1, 0.0},
{8.4, 7.1, 3.8, 7.6, 1.2, 7.2, 5.5, 2.6, 0.0},
{9.8, 8.6, 1.0, 2.6, 4.5, 1.8, 4.6, 7.5, 9.9, 0.0},
};
With this table, basically all nodes will have all other 9 nodes as neighbours. In this case, it is not possible to divide them into levels like a tree right?
I'm suppose to list the top 10 solutions to this distance table and display the best solution.
My idea to solving this problem is assuming A is the starting node. I'll compare all the other 9 neighbours of A and take the shortest edge, then i put the 2 nodes into the path list and compare the neighbours of the 2nd node, and so on..until i get a list of shortest paths through all 10 nodes and back to A. Is there any problem with this implementation?
This is my assignment and i'm not asking for solutions here. I would appreciate if u guys could help me with d concepts..thx guys..
Similar Threads
-
Replies: 1
Last Post: 05-13-2005, 06:46 AM
-
Replies: 2
Last Post: 04-18-2005, 03:03 PM
-
By Linda Solar in forum Java
Replies: 0
Last Post: 06-17-2001, 09:22 AM
-
By Linda Solar in forum Java
Replies: 0
Last Post: 06-17-2001, 09:17 AM
-
By Linda Solar in forum Java
Replies: 0
Last Post: 06-17-2001, 09:07 AM
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Development Centers
-- Android Development Center
-- Cloud Development Project Center
-- HTML5 Development Center
-- Windows Mobile Development Center
|