Shortest Path (Dijkstra) Algorithm | Competitive Programming

Single-Source Shortest Path (Dijkstra Algorithm) for a Graph:

Basics:

(1)   http://www.shafaetsplanet.com/planetcoding/?p=1500.

(2)   https://sites.google.com/site/smilitude/shortestpath.

(3)   https://sites.google.com/site/smilitude/shortestpath_problems.

(4)   http://www.progkriya.org/gyan/shortest-path.html.

(5)   https://www.youtube.com/watch?v=lAXZGERcDf4.

(6)   https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/.

(7)   https://www.geeksforgeeks.org/dijkstras-algorithm-for-adjacency-list-representation-greedy-algo-8/.

(8)   https://www.hackerearth.com/practice/algorithms/graphs/shortest-path-algorithms/tutorial/.

Problems:

(1)   Shortest path from 1 to n (Geeksforgeeks).

(2)   Dijkstra? (Codeforces).

(3)   1099 - Not the Best (Lightoj).

(4)   1281 - New Traffic System (Lightoj).

(5)   Shortest path list: 1 (Spoj), 2 (Codechef), 3 (Lightoj).

(6)   Dijkstra variation: 1 (Codeforces).

(7)   Vjudge: 1, 2., 3.

(8)   A2oj.

///Dijkstra1.cpp

///Dijkstra2.cpp

///(Data Structure: graph, cost, level, visit, parent, priority queue)

#define mx 1000

vector<int>g[mx],cost[mx];

int d[mx],par[mx];

struct node

{

    int u,w;

    node(int a,int b)

    {

        u=a;

        w=b;

    }

    bool operator < ( const node& p ) const

    {

        return w > p.w;

    }

};

int dijkstra(int s, int n)

{

    memset(d,63,sizeof(d));

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

    priority_queue<node>q;

    q.push(node(s,0));

    d[s]=0;

    while(!q.empty())

    {

        node top=q.top();

        q.pop();

        int u=top.u;

        if(u==n) return d[n];

        for(int i=0; i<(int)g[u].size(); i++)

        {

            int v=g[u][i];

            if(d[u]+cost[u][i]<d[v])

            {

                d[v]=d[u]+cost[u][i];

                par[v]=u;

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

            }

        }

    }

    return -1;

}