13,147,044 members (60,944 online)
Rate this:
See more:
```Need help in implementing the Breadth First Search (BFS) and Depth First Search (DFS) algorithms for a Travel Salesman Problem to find and print the shortest path and its total distance of the given 11 cities starting from city 1 to city 11.
city    x-coordinate    y-coordinate
1    5.681818     63.860370
2    11.850649    83.983573
3    13.798701    65.092402
4    16.883117    40.451745
5    23.782468    56.262834
6    25.000000    31.211499
7    29.951299    41.683778
8    31.331169    25.256674
9    37.175325    37.577002
10   39.935065    19.096509
11   46.834416    29.979466```
Posted 14-Sep-10 15:58pm
aspdotnetdev 14-Sep-10 23:17pm

I voted this a 1 because it seems like a homework question with no effort provided on part of the OP.
Sandeep Mewara 15-Sep-10 3:03am

Formulate your question properly. What is your issue and where are you stuck up?
cordwell 15-Sep-10 9:26am

I want to calculate the total distance of the shortest path found by BFS/DFS.
How do I integrate the distance calculation from one city to another and calculate the total distance of the path?

Rate this:

## Solution 1

This is my code, how do I integrate the distance calculation for the shortest path found

```import java.util.ArrayList;
import java.util.Queue;
import java.util.Stack;

public class Graph
{
public Node rootNode;
public ArrayList nodes=new ArrayList();
int size;
public void setRootNode(Node n)
{
this.rootNode=n;
}

public Node getRootNode()
{
return this.rootNode;
}

{
}

//This method will be called to make connect two nodes
public void connectNode(Node start,Node end)
{
{
size=nodes.size();
}

int startIndex=nodes.indexOf(start);
int endIndex=nodes.indexOf(end);
}

private Node getUnvisitedChildNode(Node n)
{

int index=nodes.indexOf(n);
int j=0;
while(j<size)
{
{
return (Node)nodes.get(j);
}
j++;
}
return null;
}

//BFS traversal of a tree is performed by the bfs() function
public void bfs()
{

//BFS uses Queue data structure
printNode(this.rootNode);
rootNode.visited=true;
while(!q.isEmpty())
{
Node n=(Node)q.remove();
Node child=null;
while((child=getUnvisitedChildNode(n))!=null)
{
child.visited=true;
printNode(child);
}
}
//Clear visited property of nodes
clearNodes();
}

//DFS traversal of a tree is performed by the dfs() function
public void dfs()
{
//DFS uses Stack data structure
Stack s=new Stack();
s.push(this.rootNode);
rootNode.visited=true;
printNode(rootNode);
while(!s.isEmpty())
{
Node n=(Node)s.peek();
Node child=getUnvisitedChildNode(n);
if(child!=null)
{
child.visited=true;
printNode(child);
s.push(child);
}
else
{
s.pop();
}
}
//Clear visited property of nodes
clearNodes();
}

//Utility methods for clearing visited property of node
private void clearNodes()
{
int i=0;
while(i<size)
{
Node n=(Node)nodes.get(i);
n.visited=false;
i++;
}
}

//Utility methods for printing the node's label
private void printNode(Node n)
{
System.out.print(n.label+" ");
}

}
```
Sandeep Mewara 15-Sep-10 3:04am

Pbhavesh17 4-Mar-14 10:24am

Node class?

Top Experts
Last 24hrsThis month
 OriginalGriff 315 CPallini 55 Graeme_Grant 50 RickZeeland 40 Jochen Arndt 30
 OriginalGriff 6,125 Graeme_Grant 5,101 ppolymorphe 1,984 Jochen Arndt 1,904 CPallini 1,855