Category Uncategorized

Dijkstra – From Source to Destination

Arunima Mandal Leave a comment

Here, I have used the adjacency matrix and Priority queue of C++ STL to implement the basic Dijkstra algorithm.

Time Complexity: O(E log(V)). This is because, for each vertex, we need to traverse all its adjacent vertices and update their distances, which takes O(E) time. Also, we use a Priority Queue which takes O(logV) time for each insertion and deletion.

Space Complexity: O(V*V). This is because, in the worst-case scenario, every vertex can be connected to every other vertex in the graph.

Code:

#include <bits/stdc++.h>

#define MAX             100005
#define INF             INT_MAX
#define pii             pair<int,int>

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

using namespace std;

int dijkstra(int src, int dst, vector<vector<pii>> &adj)
{
    vector<int> dis(MAX, INF);
    //dis[100005]={INT_MAX} ; why doesn't work(gives wrong answer) I don't know!
    dis[src]=0;

    priority_queue<pii, vector<pii>, greater<pii> >pq;
    pq.push({0, src}); // Insert source in priority queue and initialize its distance as 0.

    while(!pq.empty())
    {
        int u=pq.top().second;
        int cost=pq.top().first;
        pq.pop();

        //Optimization in the priority queue:
        /*
        Ideally, for updating the priority queue, we must delete the old value and reinsert with the
        new cost value. But, as we know that the updated cost value is always lesser than the old
        value and would be popped from the queue and visited before the old value,
        we could save time and avoid removing the old value from the queue.
        */
        if(dis[u]<cost) continue;

        for(int i=0; i<adj[u].size(); i++)
        {
            int v=adj[u][i].first;
            cost=adj[u][i].second;

            if(dis[v]>dis[u]+cost)
            {
                dis[v]=dis[u]+cost;
                pq.push({dis[v], v});
            }
        }
    }
    return dis[dst];
}

//unordered_map<string,int> mp; //for string input

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int node, edge;
    cout<<"Enter number of nodes: \n";
    cin>>node;
    cout<<"Enter number of edges: \n";
    cin>>edge;
    //int c=1;

    cout<<"Enter the edges and their corresponding cost (node node cost):"<<endl;

    vector<vector<pair<int,int> > > adj(MAX);
    //vector<pair<int,int>> adj[node]; //can also be written like this

    for(int i=0; i<edge; i++)
    {
        int from,to,cost;
        //string frm,to;
        cin>>from>>to>>cost;

//        if(mp[frm]==0)
//        {
//            mp[frm]=c;
//            c++;
//        }
//        if(mp[to]==0)
//        {
//            mp[to]=c;
//            c++;
//        }

        adj[from].push_back({to, cost});
        adj[to].push_back({from, cost}); //If undirected graph
//        g[mp[frm]].push_back(mp[to]);
//        g[mp[to]].push_back(mp[frm]); //If undirected graph
    }

    int src,dst;
    //string src,dst;

    cin>>src>>dst;

    int min_distace=dijkstra(src, dst, adj);
    //int min_distace=dijkstra(mp[src],mp[dst], adj);
    if(min_distace==INF) cout<<"No path"<<endl;
    else
    {
        cout<<"Shortest distance with min cost: "<<min_distace<<endl;
    }
    return 0;
}

SPOJ – SHPATH – The Shortest Path

Arunima Mandal Leave a comment

Problem: https://www.spoj.com/problems/SHPATH/

Level: Easy

Code:



#include <bits/stdc++.h>

#define pii     pair<int,int>
#define MAX     10004
#define INF     INT_MAX

using namespace std;

int dijkstra(int src, int dst, vector<vector<pii> > &adj)
{
    vector<int> dis(MAX, INF);
    dis[src]=0;
    priority_queue<pii, vector<pii>, greater<pii> > pq;
    pq.push({0,src});
    while(!pq.empty())
    {
        int u=pq.top().second;
        int cost=pq.top().first;
        pq.pop();
        if(dis[u]<cost) continue;

        for(int i=0; i<adj[u].size(); i++)
        {
            int v=adj[u][i].first;
            cost=adj[u][i].second;
            if(dis[u]+cost<dis[v])
            {
                dis[v]=dis[u]+cost;
                pq.push({dis[v], v});
            }
        }
    }
    return dis[dst];
}

unordered_map<string,int> ump;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int node;
        cin>>node;
        int from=1;

        vector<vector<pii> > adj(MAX);
        for(int i=0; i<node; i++)
        {
            string s;
            cin>>s;
            ump[s]=from;
            int edge;
            cin>>edge;
            for(int j=0; j<edge; j++)
            {
                int to, cost;
                cin>>to>>cost;
                adj[from].push_back({to,cost});
                adj[to].push_back({from,cost});
            }
            from++;
        }
        int query;
        cin>>query;
        for(int i=0; i<query; i++)
        {
            string src,dst;
            cin>>src>>dst;
            cout<<dijkstra(ump[src],ump[dst],adj)<<endl;
        }
    }
    return 0;
}

SPOJ – EZDIJKST – Easy Dijkstra Problem

Arunima Mandal Leave a comment

Problem: https://www.spoj.com/problems/EZDIJKST/

Note: This is a pretty straightforward problem of basic Dijkstra implementation.

In case of the Wrong Answer:

  1. Notice that the input is a Directed graph, not an undirected graph. Take care of it while creating the adjacency matrix of the graph.
  2. Notice that while pushing in the priority queue, you should push the updated cost of the current node as the first element of the pair and then the node itself as the 2nd element of the pair.

In case of the Time Limit Exceeded:

The funny thing in my case is, I got the time limit exceeded because I declared the Dijkstra function as int but was not returning any integer at first, instead I was directly printing the output inside that function. I had no idea that this fault can result in a “time limit exceeded” verdict. As I didn’t notice that at first, I debugged the code for so much time, and lastly noticed that the return type of the function should be void as I was not returning anything there. That fix made my code Accepted in SPOJ! Later, I kept the function type as int and returned the result from there.

Code:

#include <bits/stdc++.h>

#define INF             INT_MAX
#define MAX             10004
#define pii             pair<int,int>

using namespace std;

int dijkstra(int src, int dst, vector<vector<pii>> &adj)
{
    vector<int> dis(MAX, INF);
    dis[src]=0;

    priority_queue<pii, vector<pii>, greater<pii> >pq;
    pq.push({0, src}); // Insert source in priority queue and initialize its distance as 0.

    while(!pq.empty())
    {
        int u=pq.top().second;
        int cost=pq.top().first;
        pq.pop();

        //Optimization in priority queue:
        //Since the pq can hold same node more than once with different costs,
        //no need to process the nodes which has already been updated to shorter distance
        if(dis[u]<cost) continue;

        for(int i=0; i<adj[u].size(); i++)
        {
            int v=adj[u][i].first;
            cost=adj[u][i].second;

            if(dis[v]>dis[u]+cost)
            {
                dis[v]=dis[u]+cost;
                pq.push({dis[v], v});
            }
        }
    }
    return dis[dst];
}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t;
    cin>>t;
    for(int z=0; z<t; z++)
    {
        int node,edge;
        cin>>node>>edge;

        vector<vector<pair<int,int> > > adj(MAX);

        for(int i=0; i<edge; i++)
        {
            int from,to,cost;
            cin>>from>>to>>cost;
            adj[from].push_back({to, cost});
            //adj[to].push_back({from, cost}); //If undirected graph
        }

        int src,dst;
        cin>>src>>dst;

        int min_distace=dijkstra(src, dst, adj);

        if(min_distace==INF) cout<<"NO"<<endl;
        else cout<<min_distace<<endl;
    }
    return 0;
}

LeetCode 2115. Find All Possible Recipes from Given Supplies

Arunima Mandal Leave a comment

Problem Link: https://leetcode.com/problems/find-all-possible-recipes-from-given-supplies/description/

Note: Since the problem explicitly demands dependency, and the recipes are the ultimate nodes that have indegrees topological sort is the most intuitive thing that can come to mind if you know the idea of the topological sort well. I used Kahn’s algorithm here to do the topological sort.

  • Time complexity: O(n)
  • Space complexity: O(n)
class Solution {
public:
    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
        unordered_map<string, vector<string> > ump;
        unordered_map<string,int> indegree;
        vector<string> ans;
        for(int i=0; i<ingredients.size(); i++)
        {
            for(int j=0; j<ingredients[i].size(); j++)
            {
                 ump[ingredients[i][j]].push_back(recipes[i]);
                 indegree[recipes[i]]++;
            }
        }
        for(int i=0; i<supplies.size(); i++)
        {   
            for(int j=0; j<ump[supplies[i]].size(); j++)
            {
                string adj=ump[supplies[i]][j];
                indegree[adj]--;
                if(indegree[adj]==0)
                {
                    supplies.push_back(adj);
                    ans.push_back(adj);
                }
            }
        }
        return ans;
    }
};

SPOJ – DIGOKEYS – Find the Treasure

Arunima Mandal Leave a comment

Problem Link: https://www.spoj.com/problems/DIGOKEYS/

Note: This problem is pretty much a simple Graph problem. I have solved this using BFS. One thing that I was confused about was how to handle the “lexicographically smallest order of path“. But after writing the basic code, the idea that came to my mind is how about if I sort the initial graph while building that by inserting the edge nodes. If the edges are sorted, then while running the BFS, it will automatically choose the smallest numbers first! That solves our finding of “lexicographically smallest order of path”. Please feel free to comment below if you have any other ideas to implement this.

Code:

#include <bits/stdc++.h>

using namespace std;

#define MAX 100005
int parent[MAX];

void path_print(int dst, int ans)
{
    vector<int> path;
    dst=parent[dst]; //As the question suggests not to include the last destination which is obvious in every case
    while(dst!=-1)
    {
        path.push_back(dst);
        dst=parent[dst];
    }
    cout<<path[ans-1];
    for(int i=ans-2; i>=0; i--) cout<<" "<<path[i];
    cout<<endl;
}


int bfs(int src, int dst, vector<vector<int> > &g)
{
    int vis[MAX]={0};
    int dis[MAX];
    vis[src]=1;
    dis[src]=0;
    parent[MAX]={-1};
    parent[src]=-1;
    queue<int> q;
    q.push(src);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        if(u==dst) return dis[u];
        for(int i=0; i<g[u].size(); i++)
        {
            int v=g[u][i];
            if(!vis[v])
            {
                vis[v]=1;
                dis[v]=dis[u]+1;
                parent[v]=u;
                q.push(v);
            }
        }
    }
    return -1;
}

int main()
{
    int t;
    cin>>t;
    for(int z=0; z<t; z++)
    {
        int n;
        cin>>n;
        vector<vector<int> > g(MAX, vector<int> (11));
        for(int j=1; j<n; j++)
        {
            int edge;
            cin>>edge;
            int src=j;
            vector<int> des; //for sorting the edges// for "lexicographical" purpose
            for(int k=0; k<edge; k++)
            {
                int dst;
                cin>>dst;
                des.push_back(dst);
            }
            sort(des.begin(), des.end()); //We are doing this only to ensure the "lexicographically smallest" order of path
            for(int k=0; k<des.size(); k++)
            {
                g[src].push_back(des[k]);
            }

        }
        int ans=bfs(1,n, g);
        cout<<ans<<endl;
        if(ans!=-1)
        {
            path_print(n, ans);
        }
        cout<<endl;
    }
    return 0;
}