short path algorithm

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.

Code:

---

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.

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! ;)

Quote:

---

Originally Posted by vladic256

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