Shortest path in an unweighted graph, using user input in C++

Question

As I was practicing C++ today, I came across a code which finds the shortest path in an unweighted graph using BFS and outputs the length of the path and the vertices it travelled through. I attempted to change up this code by introducing user input. First, the user has to input two integers, lets say N and M. N holds the number of vertices and M holds the number of edges. The next M lines contain two integers, which indicates an undirected edge between two nodes.

I attempted to change the code in accordance to this, but I ran into a number of problems.

The first problem is that if I use gcc, the program will end after the for loop runs once in the main function. However, if I use clang, the program runs fine. But there is an other issue and it relates to a very specific input.

The following input: 3 3 1 3 1 2 2 3

should return 1, but sometimes (specifically when I enter the input line by line) it returns the message: "Given source and destination are not connected". It is completely random.

The code is below:

#include <iostream>
#include <vector>
#include <list>

using namespace std;


bool BFS(vector<int> adjList[], int source, int dest, int numOfVertices, int pred[], int dist[]);
void printShortestDistance(vector<int> adjList[], int s, int dest, int numOfVertices);


int main()
{
    int numOfVertices, numOfEdges;
    cin >> numOfVertices >> numOfEdges;

    vector<int> adjList[numOfVertices];

    if (2 <= numOfVertices && numOfVertices <= 1e5 && 1 <= numOfEdges && numOfEdges <= 1e5)
    {
        for (int i = 0; i < numOfEdges; i++)
        {
            int node1, node2;
            cin >> node1 >> node2;

            if ((1 <= node1) && (1 <= node2) && (node1 <= numOfVertices) && (node2 <= numOfVertices) && (node1 != node2))
            {
                adjList[node1].push_back(node2);
                adjList[node2].push_back(node1);
            }
            else{ return EXIT_FAILURE; }
        }

        int source = 1;
        int dest = numOfVertices;
        printShortestDistance(adjList, source, dest, numOfVertices);
    }
}


void printShortestDistance(vector<int> adjList[], int source, int dest, int numOfVertices)
{
    int pred[numOfVertices];
    int dist[numOfVertices];

    if (BFS(adjList, source, dest, numOfVertices, pred, dist) == false)
    {
        cout << "Given source and destination are not connected";
        return;
    }

    vector<int> path;
    int crawl = dest;
    path.push_back(crawl);
    while (pred[crawl] != -1)
    {
        path.push_back(pred[crawl]);
        crawl = pred[crawl];
    }

    cout << "Shortest path length is : " << dist[dest];

    cout << "\nPath is::\n";
    for (int i = path.size() - 1; i >= 0; i--)
        cout << path[i] << " ";
}


bool BFS(vector<int> adjList[], int source, int dest, int numOfVertices, int pred[], int dist[])
{
    list<int> queue;
    bool visited[numOfVertices];

    for (int i = 0; i < numOfVertices; i++)
    {
        visited[i] = false;
        dist[i] = INT_MAX;
        pred[i] = -1;
    }

    visited[source] = true;
    dist[source] = 0;
    queue.push_back(source);

    while (!queue.empty())
    {
        int u = queue.front();
        queue.pop_front();

        for (int i = 0; i < adjList[u].size(); i++)
        {
            if (visited[adjList[u][i]] == false)
            {
                visited[adjList[u][i]] = true;
                dist[adjList[u][i]] = dist[u] + 1;
                pred[adjList[u][i]] = u;
                queue.push_back(adjList[u][i]);
 
                // We stop BFS when we find
                // destination.
                if (adjList[u][i] == dest)
                    return true;
            }
        }
    }

    return false;
}

Please extract a [mcve]. As a new user here, please also take the [tour] and read [ask]. Also, one more thing to look at, the changes between the original code and your modified version. — Ulrich Eckhardt, Dec 17 '22 at 19:19

score 1 · Answer 1 · answered Dec 17 '22 at 18:46

Remember that vectors in C++ are 0-based.

In your example, numOfVertices and numOfEdges are both 3, so node 3 will lead to out-of-bound access. Either change your input to 0-based node numbers or use node1-1 and node2-1.

See also

Vector going out of bounds without giving error

and the accepted answer.

ravenspoint · Answer 2 · 2022-12-17T18:07:13.530

"First, the user has to input two integers, lets say N and M. N holds the number of vertices and M holds the number of edges."

This is not a good idea. Humans are terrible at counting, while computers are pretty good at it. So do not make your users count the vertices and edges - they will often get it wrong and cause chaos.

Just input the start and ending nodes of an edge. If a node is already present in the data structure, connect it. If node not already present then add it and then connect it.

You will have much happier users!

I see that you have decided to store your graph in an adjacency list. This is a perfectly reasonable idea, but the snag is that it is quite a challenge to code. This seems to be your first attempt to code a graph theory problem, so I recommend that you use an adjacency matrix instead since it is much easier to code.

For small graphs the difference is insignificant, so you need only consider switching to the more complicate adjacency list when you are working with enormous graphs ( many thousands of nodes )

Thank you for your response! But sadly, I need it to use those specific numbers as user input because I am planning to use this as basis for an other exercise which requires these inputs. I wish I could just choose your suggestion, but I cannot. — LosCocos, Dec 17 '22 at 18:08
You need to rethink your application design. In the meantime just ignore the N and M input values - you do not need them and they will often be wrong in any case — ravenspoint, Dec 17 '22 at 18:33

Shortest path in an unweighted graph, using user input in C++

2 Answers2