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

general
,
1

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??

1 Like
2

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

1 Like
3

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));
      }

    }
   }
}
2 Likes
4

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

5 
You can refer here http://zobayer.blogspot.de/2009/12/dijkstras-algorithm-in-c.html
2 Likes
6

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

7

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!

8

It was helpful

1 Like
9

it was helpful

1 Like
10

It Helps …

1 Like
11

It’s Helpful …

1 Like