Single source shortest path ( SSSP - Dijkstra )

কোন গ্রাফের একটা নোড থেকে আরেকটা নোড এর মিনিমাম দূরত্ব বের করাই  dijkstra এর কাজ।
অনলাইনে সার্চ দিলেই ভাল ভাল টিওটোরিয়াল পাবে শেখার জন্যে।
Dijkstra animation

শিখতে হবেঃ

• STL
  1. Priority Queue ( push, pop, top, size, empty )
  Priority Queue একটি Data structure যেখানে element গুলো সবসময়  sorted থাকে।
  Priority Queue কি ও কি করে শুধু সেটা জানলেই হবে আপাতত। Data structure কোর্স করার সময় বিস্তারিত তখন জানতে পারবে।
  

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

#define MAX 1000
#define INF (1<<30) // 2^30

struct data{
    int v,w;

    // how the data'll be sorted in priority queue
    bool operator<(const data &p)const
    {
        return p.w<w; // in ascending order
    }
};

/*
You don't need to understand how does the following function work in the
structure right now.

bool operator<(const data &p)const
{
    return p.w<w;
}

You'll understand it later. Only remember if you write
return p.w<w; // It'll sort in ascending order of w
return p.w>w; // It'll sort in descending order of w
*/

vector<data>con[MAX]; // graph connection
int dis[MAX]; // distance from the start node

int dijkstra(int start,int end)
{

    priority_queue<data>Q;
    for(int i=0;i<MAX;i++) dis[i] = INF; 
    // at first set infinite distance from start node to every node 

    data tmp;
    tmp.v = start;
    tmp.w = 0;
    pq.push(tmp);
    dis[start] = 0;

    while(!Q.empty())
    {
        int u = Q.top().v;
        int w_u = Q.top.w;
        Q.pop();

        // if(u==end) return dis[end]; It works also;

        for(int i=0;i<SZ(con[u]);i++)
        {
            int v = con[u][i].v;
            int w_v = con[u][i].w;

            if( w_u+w_v < dis[v] )
            {
                dis[v] = w_u + w_v;

                tmp.v = v;
                tmp.w = dis[v];

                pq.push(tmp);
            }
        }
    }

    return dis[end];
}

Problem

UVA - 341, 920, 10801, 10986, 10000