short path algorithm

[vladic256]

Hello, I currently have a program that detects the shortest path by using breath first search. Currently my program reads a file like this.

A H
A D
A J
J D
J K
J E
F H
F D
F B
K B
B I
G I
G K
C E
K I
E K

This works just fine because every road is connected at some point. So if I type A to I it would give me A J K I.

My problem is that my program has to read in a bigger road file, but NOT all the roads connect. for example:
170 157
170 171
172 173
171 174

road 172 and 173 does not connect to any other roads

Since am using breath-first search am assigning every node a NODE LEVEL starting with 0 till the end of the road file. These get assigned via a queue that I implement thinking that all the roads are connected. By default all nodes have level -1 because they have not been visited.


This code will create the node level.

queque.push_back(t[0]);  //start my queue at the beginning of the file.


while(queque.empty()!= true)
{

	for(int i = 0; i< queque[0]->next.size(); i++)
	{
		if(queque[0]->next[i]->node_level == -1)
		{
			

			queque[0]->next[i]->node_level = (queque[0]->node_level) + 1;

			queque.push_back(queque[0]->next[i]);

			
		}
	}

	queque.erase(queque.begin()+0);

}

I know the problem am having is that I can't assigned a node level because they don't get added to the queue. I was just wondering if you guys have any ideas of how to work around this problem. I don't need coding just some ideas.

[Amleto]

you said you have assumed all roads are connected. Simply, you have to remove that assumption and follow through the consequences.

In general, showing only a snippet is not very helpful, escpecially when you have not shown how you have parsed the file into queque / t / next.

Since your problem is that some things are not added to the queue, I would look at the code that adds things to the queue! no point in onyl showing us how you use the queue, when the problem has already happened!

[Paul McKenzie]

Since am using breath-first search am assigning every node a NODE LEVEL starting with 0 till the end of the road file. These get assigned via a queue that I implement thinking that all the roads are connected.

Forget about programming and figure out how you wold do this on paper.

One possible fix is to start to build a separate graph if you detect that the road is not connected. Basically, your data set contains more than one graph -- your job is to build these graphs as separate entities instead of trying to stick everything in one graph.

Regards,

Paul McKenzie