Question

You need to start doing your CST370 homework, but you don't really feel like it. You decide
to take the longest route from your current location on campus to where you plan to do
your homework to procrastinate a bit. You're given a graph representing CSUMB's campus,
and your goal is to nd the path with the most stops to your homework destination without
visiting any location more than once.

Input
• The first line contains your current location.
• The second line contains the location where you'll do your homework.
• The remaining input describes a graph where each edge means two locations are adjacent.
{ The next line contains an integer n, the number of locations on campus.
{ The next n lines each contain one location. This makes up an array of verticies.
{ The next line contains two space-separated integers: n e
{ The next e lines each contain two space-separated integers a and b describing an
edge from the vertex indexed at a to the vertex indexed at b.
Constraints
You can assume the campus locations form a connected, undirected graph. The graph is connected and undirected.
Output
The length of the longest possible path you can take your current location to your homework
destination on a single line.

How do you solve this problem with breadth first search in C++?

Sample Input:

BIT
East Campus
9
Pool
Library
Gym
BIT
Construction Site
Student Center
East Campus
VPA Building
Otter Express
9 22
0 2
0 4
1 3
1 4
2 0
2 8
3 4
3 1
3 8
3 5
4 3
4 1
4 0
5 8
5 3
6 7
7 6
7 8
8 5
8 3
8 2
8 7

Sample Output:

7

Answer 1

# Please leave a thumbs up.

The problem of finding longest path between any two vertices of a graph is the NP Hard problem.

Also, simple way to do this is to use adjency matrix or adjency list.

Also, you can use floyd warshall algorithm that uses dynamic programming to find shortest path and tweak some parts of it to find longest path between two vertices.

Heres a code to find the longest path in your grapgh.

// C++ program to find longest path

#include <bits/stdc++.h>

#include<string.h>

using namespace std;

  

// This class represents a undirected graph using adjacency list

class Graph

{

    int V;              // No. of vertices

    list<int> *adj;     // Pointer to an array containing

                        // adjacency lists

public:

    Graph(int V);              // Constructor

    void addEdge(int v, int w);// function to add an edge to graph

    void longestPathLength(); // prints longest path of the tree

    pair<int, int> bfs(int u); // function returns maximum distant

                               // node from u with its distance

};

  

Graph::Graph(int V)

{

    this->V = V;

    adj = new list<int>[V];

}

  

void Graph::addEdge(int v, int w)

{

    adj[v].push_back(w);    // Add w to v’s list.

    adj[w].push_back(v);    // Since the graph is undirected

}

  

// method returns farthest node and its distance from node u

pair<int, int> Graph::bfs(int u)

{

    // mark all distance with -1

    int dis[V];

    memset(dis, -1, sizeof(dis));

  

    queue<int> q;

    q.push(u);

  

    // distance of u from u will be 0

    dis[u] = 0;

  

    while (!q.empty())

    {

        int t = q.front();       q.pop();

  

        // loop for all adjacent nodes of node-t

        for (auto it = adj[t].begin(); it != adj[t].end(); it++)

        {

            int v = *it;

  

            // push node into queue only if

            // it is not visited already

            if (dis[v] == -1)

            {

                q.push(v);

  

                // make distance of v, one more

                // than distance of t

                dis[v] = dis[t] + 1;

            }

        }

    }

  

    int maxDis = 0;

    int nodeIdx;

  

    // get farthest node distance and its index

    for (int i = 0; i < V; i++)

    {

        if (dis[i] > maxDis)

        {

            maxDis = dis[i];

            nodeIdx = i;

        }

    }

    return make_pair(nodeIdx, maxDis);

}

  

// method prints longest path of given tree

int Graph::longestPathLength(int s)

{

    pair<int, int> t1, t2;

  

    // first bfs to find one end point of

    // longest path

    t1 = bfs(s);

  

    // second bfs to find actual longest path

    t2 = bfs(t1.first);

  

return t2.second;

}

  

// Driver code to test above methods

int main()

{

string myLocation;

cin>>myLocation;

string dest;

cin>>dest;

int totalLocations;

cin>>totalLocations;

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

string loc;

cin>>loc;// here each location is represented by numbers ex pool=0,library=2 and so on.

}

    // Create a graph given in the example

int TotalLoc;

cin>>TotalLoc;

int totaledges;

cin>>totaledges;

    Graph g(totalLocations);

for(i=0;i<totaledges;i++){

int v1;

cin>>v1;

int v2;

cin>>v2;

    g.addEdge(v1, v2);

}

  

int length= g.longestPathLength();

cout<<length;

    return 0;

}