C++ Trouble with Understanding BFS to find Shortest Path

Question

I have a simple graph and my assignment is to find the shortest path between two nodes. I've done my best to read through the BFS pseudocode and examples but it's just not clicking.

My nodes are stored in an adjacency list, (at the moment I'm not concerned with edge weights) Here's a visual of the data: The first column is the vector element, the row to it's immediate left is another vector. The vector element number represents the number of the corresponding node.

=====================================
0  |  (1, 100), (3, 50), (7, 100)
1  |  (0, 100), (4, 50), (5, 10) 
2  |  (3, 1000), (4, 200), (6, 1000) 
3  |  (0, 50), (2, 1000) 
4  |  (1, 50), (2, 200), (6, 100) 
5  |  (1, 10), (6, 50), (7, 2000) 
6  |  (2, 1000), (4, 100), (5, 50) 
7  |  (0, 100), (5, 2000)

I'm trying to implement a BFS via the pseudocode I found on wikipedia but I'm not getting it. My adjancency list is stored in a vector: vector<vector <vertex> > adjList; vertex is a struct of two int's 1)node and 2)weight (again I'm not really concerned with weights right now but I'm leaving this struct setup this way to modify later)

My implementation is pretty basic:

vector<vector <vertex> > adjList;      // the vector adjacency list

// the start and end vertices are passed into the function
int startV;     //num of start node
int endV;       //num of destination node

bool visited = false, done = false;    //control         

vector<int> marked, path;              // holds visited and final path

Queue<int> Q;                          // Q for BFS
Q.push(startV);                        // enqueue BFS

while (!Q.empty() && !done) {

    int t = Q.front(); Q.pop();        // mark and pop(back)
    marked.push_back(t);               // push back start node onto marked

    if (t == endV)                     // if t is our destination
        done = true;                   // done, get out of here

    size_t adjE = adjList[t].size();   // degree of this node

    for (int i = 0; i < adjE; i++) {

        int u = adjList[t][i].node;    // visit each adjacent node

        for (int j = 0; j < marked.size(); j++) {

           if (marked[j] == u)         // test if node has been marked
               visited = true;  
           }
                                       // check if this node has
           if (!visited) {             // already been visited
              marked.push_back(u);     // if not enqueue
              Q.push(u);
           }
        }
    }
}

I know there has to be something wrong with my implementation. I'm just not seeing what is.

Update: I solved this by using a multimap approach. A detailed explanation is here: Traverse MultiMap to Find Path from a Given Value to a Given Key

Answer 1

I think your logic about finding visited nodes is incorrect. Try

...
int u = adjList[t][i].node;

visited = false;
for (int j = 0; j < marked.size(); j++) {
    // std::find() does essentially all this for you. Check it out.
    if (marked[j] == u) {
        visited = true;
    }
}

if (!visited) {
    marked.push_back(u);
    Q.push(u);
}