You are not logged in. Please login at www.codechef.com to post your questions!

×

Dijkstar's Algo to find shortest path from 1 to N

In The Dijkstra's algo we need to extract the minimum of D where D is the distance from node 0. But as D gets updated with the distance randomly how could we extract the minimum. Eg: Let at an instance we have the below array and we have used the node 0(its distance to itself is always 0) and accordingly its adjacent node2 and node5 get updated with distance from node 0. D: 0 INF 3 INF INF 1 INF

If we use O(n) then ultimately we are using O(n^2) as we will be updating the adjacent of node 5 and again extracting the minimum by using O(n). Is there a better approach to extract the minimum??

asked 28 Jun '15, 14:00

aniruddha_paul's gravatar image

2★aniruddha_paul
35213
accept rate: 0%

edited 28 Jun '15, 14:03


link

answered 29 Jun '15, 18:52

pallesai's gravatar image

4★pallesai
176831
accept rate: 17%

Yes..use heap to store these. Priority queue is the key.

link

answered 28 Jun '15, 14:26

shivam9753's gravatar image

4★shivam9753
696112
accept rate: 17%

void dijkstras(int start,vector< pii > G[],int d[])
{
  int u,c,v,w;
   priority_queue< pii, vector< pii >, greater< pii > > Q;
    memset(d, 0x3f, sizeof d);
    Q.push(pii(0,start));
    d[start]=0;

    while(!Q.empty())
     {

     c=Q.top().first;
     u=Q.top().second;
     Q.pop();
     if(d[u]<c)
     continue;
       for(int i=0;i<G[u].size();i++)
     {
      v=G[u][i].first;
      w=G[u][i].second;
     if(d[v]>d[u]+w)
     {
     d[v]=d[u]+w;
      Q.push(pii(d[v],v));
      }

    }
   }
}
link

answered 28 Jun '15, 14:29

shivam9753's gravatar image

4★shivam9753
696112
accept rate: 17%

here G is vector<pair<int,int>> G[]. every vertice u will have a pair v(edge u->v) and w(weight).

(28 Jun '15, 14:31) shivam97534★

It was helpful

link

answered 19 Nov '16, 20:42

lud1161's gravatar image

2★lud1161
1418
accept rate: 58%

edited 19 Nov '16, 20:43

it was helpful

link

answered 19 Nov '16, 21:01

thunder_blade's gravatar image

5★thunder_blade
372
accept rate: 0%

Answer is hidden as author is suspended. Click here to view.

answered 19 Nov '16, 22:47

tester1161's gravatar image

0★tester1161
(suspended)
accept rate: 0%

Answer is hidden as author is suspended. Click here to view.

answered 19 Nov '16, 22:49

tester1161's gravatar image

0★tester1161
(suspended)
accept rate: 0%

I think function can be helpful.

Only integer -1 in case of no path.

void dijkstra(int start, vector<pii>G[])
 {
     long long int dist[1000],prev[1000];

     priority_queue<pii,vector<pii>,greater<pii> >q;
     vector<int>path;

     for(int i=1; i<=n; i++)
     {
        dist[i]=infinity;
        prev[i]=-1;
     }

     q.push(pii(0,start));
     dist[start]=0;

     while(!q.empty())
     {
        u=q.top().second;
        q.pop();
        for(int i=0; i<G[u].size();i++)
        {
            v=G[u][i].second;
            w=G[u][i].first;
            if(dist[u]+w<dist[v])
            {

                dist[v]=dist[u]+w;
                prev[v]=u;
                q.push(pii(dist[v],v));
            }
        }
     }


    if(prev[n]==-1)
    {
       cout<<"-1"<<endl;
    }

    else
    {
        u=n;
        while(u!=-1)
        {
            path.push_back((u));
            u=prev[u];
        }

        for(int i=path.size()-1; i>=0; i--)
        {
           cout<<path[i]<<" ";
        }
        cout<<endl;
    }
}

Reference : Blog

link

answered 19 Nov '16, 14:17

rashedcs's gravatar image

2★rashedcs
49761756
accept rate: 4%

edited 24 Nov '16, 22:05

The trick here is to use a priority queue , where each and every distance would be pushed. Next we will eject elements one by one , note that if the distance is already ejected and copied in the minimum distance vector , it will be ejected but not copied into the min distance vector , here is an implementation of it , I made for Free Tickets (INOI 2012) problem,

int dijkstra(std::vector<std::vector<int> >graph,int vertex,int size){
    std::vector<int>map(size,INT_MAX);
    std::priority_queue<distances>heap;
    std::vector<int>visited(size,false);
    map[vertex] = 0;
    for(int i=0;i<size;i++){
        if(i == vertex){
            continue;
        }
        if(graph[vertex][i] != NIL){
            distances a;
            a.index = i;
            a.dist = graph[vertex][i];
            heap.push(a);
        }else{
            distances a;
            a.index = i;
            a.dist = INT_MAX;
            heap.push(a);
        }
    }
    visited[vertex] = true;
    while(!heap.empty()){
        distances top = heap.top();
        heap.pop();
        int ind = top.index;
        int distance = top.dist;
        if(visited[ind]){
            continue;
        }
        //std::cout << ind << ' ';
        map[ind] = distance;
        visited[ind] = true;
        for(int i=0;i<size;i++){
            if(graph[ind][i] != NIL && !visited[i]){
                distances a;
                a.index = i;
                //std::cout << ind << ' ' << distance << ' ';
                a.dist = graph[ind][i] + distance;
                if( a.dist < map[i]){
                    heap.push(a);
                }
            }
        }
    }
    //std::cout << std::endl;
    int ret = *std::max_element(map.begin(),map.end());
    return ret;
}

Hope it helps , cheers!

link

answered 19 Nov '16, 14:37

mz54's gravatar image

2★mz54
15613
accept rate: 30%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,236
×180

question asked: 28 Jun '15, 14:00

question was seen: 2,429 times

last updated: 24 Nov '16, 22:05