CODEWITHSUNDEEP
c++algorithm
user3840069
user3840069

Reputation: 765

Minimum distance between two nodes in tree

Given a unweighted and undirected tree with N nodes and N-1 edges I need to find minimum distance between source S and destination D.

Code :

vector<vector<int> >G(110);

bool check(int node,vector<int>path)
{
    for(int i=0;i<path.size();++i)
    {
        if(path[i]==node)
           return false;
    }
    return true;
}
int findMinpath(int source,int target,int totalnode,int totaledge)
{
    vector<int>path;
    path.push_back(source);
    queue<vector<int> >q;
    q.push(path);
    while(!q.empty())
    {
        path=q.front();
        q.pop();
        int lastNode=path[path.size()-1];
        if(lastNode==target)
        {
            return path.size()-1;
        }
        for(int i=0;i<G[lastNode].size();++i){
            if(check(G[lastNode][i],path)){
                vector<int>new_path(path.begin(),path.end());
                new_path.push_back(G[lastNode][i]);
                q.push(new_path);
         }}}
    return 1;
}

And then in main :

int N,S,E;
cin>>N>>S>>E;
for(int i=1;i<=N-1;++i)
{
    int u,v;
    cin>>u>>v;
    G[u].push_back(v);
    G[v].push_back(u);
 }
 cout<<findpaths(S,E,N,N-1)<<"\n";

Can it be further optimised as I need just minimum distance between S and E

Upvotes: 1

Views: 1338

Answers (1)

IVlad
IVlad

Reputation: 43477

You seem to be pushing vectors to your queue, each vector containing the actual path so far. But you can get away with only pushing nodes, since you only use the last node in those vectors anyway, and instead store the distance to each node from the source.

This will be much faster because you won't be copying vectors at each step.

Keep track of the distances in an array and also use them to make sure you don't visit a node multiple times.

Untested, but should get the point across:

int distance[110 + 1]; // d[i] = distance from source to i, initialize with a large number

int findMinpath(int source,int target,int totalnode,int totaledge)
{
    for (int i = 0; i <= totalnode; ++i)
    {
        distance[i] = 2000000000;
    }

    queue<int> q;
    q.push(source);
    distance[source] = 0;
    while(!q.empty())
    {
        node=q.front();
        q.pop();
        if(node==target)
        {
            return distance[node];
        }
        for(int i=0;i<G[node].size();++i){
            if(distance[node] + 1 < distance[ G[node][i] ]){
                distance[ G[node][i] ] = distance[node] + 1
                q.push(G[node][i]);
         }}}
    return 1;
}

Upvotes: 1

Related Questions