Search

aarifshuvo

First blog post

This is your very first post. Click the Edit link to modify or delete it, or start a new post. If you like, use this post to tell readers why you started this blog and what you plan to do with it.

Featured post

Deejekastrra Deejekastrra

ডায়াক্সট্রাতে কি করে মানুষজন? -_-

একটা গ্রাফ দেয়া থাকবে ওয়েটেড আনডিরেক্টেড অর ডিরেক্টেড গ্রাফ ।

একটা সোর্স থাকে, সোর্স থেকে পুরা গ্রাফের সবগুলা কানেক্টেড নোড সবচেয়ে কম কস্টে এক্সাক্টলি একবার কিভাবে ট্রাভারস করে আসা যায় ।

মানে মিনিমাম কস্ট এ ওই গিভেন সোর্স থেকে সিংগেল সোর্স শরটেস্ট পাথ টা কিভাবে বের করা যায় সেটা বের করাই ডায়াক্সট্রার উদ্দেশ্য ।

সোর্স থেকে স্প্যানিং ট্রি এর মত ট্রাভারস করে এইটা।

————————————————————————————

Start from the source vertex…

1. Finding Cheapest Adjacent Unknown Vertex

2. Mark That as True i.e. visited

3. go to its adjacent nodes

4. if already visited then skip

5. if the next adjacent is unvisited, then update its dist array with new cumulative cost from that single source

6. in this manner visit all the nodes and their adjacent nodes

after traversing all….

we can print the shortest path from the src to all the nodes individually using par[] array and recursion we can print all the shortest path available from the sorce nodes.

একটা ডায়াক্সট্রা চালায়ে দেন অটোমেটিক সবগুলা সোর্স থেকে সবগুলা নোডের শরটেস্ট পাথ পাই আমরা ।

দেন রিকারশন দিয়ে সোর্স থেকে দরকার অনুযায়ী ইউজড মিনিমাম কস্টের পাথ টা প্রিন্ট করে দিতে হবে ।

—————————————————————————————

একটা বুলিয়ান এরে লাগবে নোডগুলা কোনটা ভিজিটেড কোনটা নন ভিজিটেড চেক দেয়ার জন্য ।

পাথ প্রিন্টিং এর জন্য par অ্যারে লাগবে এন্ড সোর্স থেকে সব নোডের ডিসটেন্স এর জন্য d অ্যারে লাগবে।

  bool mark[100007];

  int par[100007];

  ll d[100007];

কোন নোড এর এজেসেন্ট কোন কোন নোড আছে তার জন্য vector<int> adj[100007] , ওইসব নোডের কোনটাতে যেতে এর এজেসেন্ট থেকে কত কস্ট লাগে সেটি জমা রাখার জন্য ওই এজেসেন্ট ভেক্টরের প্যারালালে একটা কস্ট ভেক্টর লাগেবে । যেখানে adj[u][i] , cost[u][i] এরকম হিসেবে ইউজ করা হবে।

 

    vector <int> adj[1000007];

    vector <ll> cost[100007];

    scll(n,e);

    REP(i,e)

    {

        scll(x,y),scl(z);

        adj[x].push_back(y);

        adj[y].push_back(x);

        cost[x].push_back(z);

        cost[y].push_back(z);

    }

বিএফেস এ কিউ ইউজ করতা এখানে ইউজ করতে হবে প্রায়োরিটি কিউ, মডিফাইড প্রায়োরিটি কিউ ছোট থেকে বড়তে সাজানো প্রায়োরিটি কিউ, যেটাতে আমরা প্রত্যেকটা নোড এবং ওই নোডের রেসপেক্টিভ কস্ট পুশ করব প্রায়োরিটি কিউতে। এই প্রায়োরিটি কিউ তে কস্ট অনুযায়ি সরট করা থাকবে যেই নোডের কস্ট (কোন কস্ট !!! ) কম তাকে কিউতে আগে উপরে ফ্রন্টে রাখবে।

নোড নামে একটা স্ট্রাকচার নিব । ওইখানে কন্সট্রাক্টর দিয়ে অটো ইনপুট নিব। আর ভেতরে আবার অপারেটর ওভারলোড করব । কস্ট অনুযায়ী ছোট থেকে বড় অনুযায়ী ।

struct node

{

    int city;

    ll cst;

    node(int _city, ll _cst)

    {

        city = _city;

        cst = _cst;

    }

    bool operator < (const node &p) const

    {

        return (cst > p.cst);

    }

};

এক্সট্রা কাজ শেষ । এবার আসল ডায়াক্সট্রা শুরু হবে ।

শুরুতে ১ থেকে এন পর্যন্ত সব নোডের d[i] মানে ডিসটেন্স ইনফিনিটি করতে হবে । আর পাথ প্রিন্টের সুবিধার জন্য সবাইকে নিজেকে নিজের প্যারেন্ট বানাতে হবে।  আর সোরস নোডের ডিস্ট অ্যারেতে জিরো বসাও।

void diakstra()

{

    int u,v,cst;

    FOR(i,1,n) d[i]=inf, par[i] = i;

    priority_queue<node> pq;

    pq.push(node(1,0));

    d[1] = 0;

}

 while(!pq.empty())

    {

        node x = pq.top();

        pq.pop();

        int u = x.city;

এখন আমার প্রায়োরিটি কিউ তে যেই নোড আছে সেইটা কে u ধরে মার্ক 1 করে দিব । তারপর তার এজেসেন্ট এ যেগুলা আছে তাদের মধ্যে লুপ চালায়ে দেখতে হবে । কারো ডিসটেন্স কে রিলেক্স করে আপডেট করা যায় কিনা!

যদি ওই এজেসেন্ট নোডটা আগে থেকে ভিজিটেড না থাকে এন্ড সেটাকে আপডেট করা যায় দেন, ওই নোড এবং নতুন ডিসটেন্স টা পুশ করতে হবে। আর par[v] = u করে দিতে হবে।

   if(mark[u]==0)

        {

            mark[u]==1;

            REP(i,SZ(adj[u]))

            {

                v = adj[u][i];

                cst = cost[u][i];

                if(mark[v]==0)

                {

                    if(d[u]+cst < d[v])

                    {

                        d[v] = d[u]+cst;

                        par[v] = u;

                        pq.push(node(v,d[v]));

                    }

                }

            }

        }

[ভুল থাকতে পারে পারলে ঠিক কইরা দেন, নাইলে চুপ কইরা থাকেন :। ]

Second Shortest Path Using Dijkstra: 

Code:

 

 #include <bits/stdc++.h>

#define ll long long

#define SZ(x) ((int)(x).size())

#define scl(x) scanf(“%lld”, &x)

#define scll(x,y) scanf(“%lld %lld”, &x, &y)

#define ALL(x) (x).begin(),(x).end()

#define REP(i,n) for(int i=0;i<n;i++)

#define REV(i,n) for(int i=n-1;i>=0;i–)

#define FOR(i,a,b) for(int i=a;i<=b;i++)

#define pri(a) cout<<a<<endl

#define prii(a,b) cout<<a<<” “<<b<<endl

using namespace std;

#define inf 999999999999999

bool mark[100007];

int par[100007];

ll d[100007];

ll n,e;

vector <int> adj[1000007];

vector <ll> cost[1000007];

struct node

{

    int city;

    ll cst;

    node(int ci, int cs)

    {

        city = ci;

        cst = cs;

    }

    bool operator < (const node &p) const

    {

        return (cst > p.cst);

    }

};

void diakstra()

{

    int u,v,cst;

    FOR(i,1,n) d[i]=inf, par[i] = i;

    priority_queue<node> pq;

    pq.push(node(1,0)); // 1 number node theke oitar init cost 0

    d[1] = 0;

    while(!pq.empty())

    {

        node x = pq.top();

        pq.pop();

        int u = x.city;

        if(mark[u]==0)

        {

            mark[u]==1;

            REP(i,SZ(adj[u]))

            {

                v = adj[u][i];

                cst = cost[u][i];

                if(mark[v]==0)

                {

                    if(d[u]+cst < d[v])

                    {

                        d[v] = d[u]+cst;

                        par[v] = u;

                        pq.push(node(v,d[v]));

                    }

                }

            }

        }

    }

}

void prntpath(int s)

{

    if(s==par[s])

    {

        printf(“%d “, s);

        return;

    }

    prntpath(par[s]);

    printf(“%d “, s);

}

int main()

{

    ll x,y,z;

    scll(n,e);

    REP(i,e)

    {

        scll(x,y),scl(z);

        adj[x].push_back(y);

        adj[y].push_back(x);

        cost[x].push_back(z);

        cost[y].push_back(z);

    }

    diakstra();

    if(d[n]>=inf)

    {

        printf(“-1\n”);

    }

    else

    {

        prntpath(n);

    }

    return 0;

}

Problems for Dijkastra:

http://codeforces.com/problemset/problem/20/C

UVa 10986 Sending Email

Blog post title

This is an additional placeholder post. Click the Edit link to modify or delete it, or start a new post.

Blog post title

This is an additional placeholder post. Click the Edit link to modify or delete it, or start a new post.

Create a free website or blog at WordPress.com.

Up ↑