Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
See more: C# Java .NET Python
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 16:58pm
Comments
aspdotnetdev at 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 at 15-Sep-10 3:03am
   
Formulate your question properly. What is your issue and where are you stuck up?
cordwell at 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?

1 solution

Rate this: bad
good
Please Sign up or sign in to vote.

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.LinkedList;
import java.util.Queue;
import java.util.Stack;
 

public class Graph 
{
	public Node rootNode;
	public ArrayList nodes=new ArrayList();
	public int[][] adjMatrix;//Edges will be represented as adjacency Matrix
	int size;
	public void setRootNode(Node n)
	{
		this.rootNode=n;
	}
	
	public Node getRootNode()
	{
		return this.rootNode;
	}
	
	public void addNode(Node n)
	{
		nodes.add(n);
	}
	
	//This method will be called to make connect two nodes
	public void connectNode(Node start,Node end)
	{
		if(adjMatrix==null)
		{
			size=nodes.size();
			adjMatrix=new int[size][size];
		}
 
		int startIndex=nodes.indexOf(start);
		int endIndex=nodes.indexOf(end);
		adjMatrix[startIndex][endIndex]=1;
		adjMatrix[endIndex][startIndex]=1;
	}
	
	private Node getUnvisitedChildNode(Node n)
	{
		
		int index=nodes.indexOf(n);
		int j=0;
		while(j<size)
		{
			if(adjMatrix[index][j]==1 && ((Node)nodes.get(j)).visited==false)
			{
				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
		Queue q=new LinkedList();
		q.add(this.rootNode);
		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);
				q.add(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+" ");
	}
 
	
	
	
 
}
 
  Permalink  
Comments
Sandeep Mewara at 15-Sep-10 3:04am
   
Not an answer. Use' Improve Question' to edit/update your question.
Pbhavesh17 at 4-Mar-14 10:24am
   
Node class?

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



Advertise | Privacy | Mobile
Web04 | 2.8.1411022.1 | Last Updated 14 Sep 2010
Copyright © CodeProject, 1999-2014
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100