Click here to Skip to main content
12,063,452 members (70,372 online)
Rate this:
 
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 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?

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 15-Sep-10 3:04am
   
Not an answer. Use' Improve Question' to edit/update your question.
Pbhavesh17 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)

  Print Answers RSS
Top Experts
Last 24hrsThis month


Advertise | Privacy | Mobile
Web04 | 2.8.160204.4 | Last Updated 14 Sep 2010
Copyright © CodeProject, 1999-2016
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