Gajanana's blog

By Gajanana, history, 3 months ago, In English

This is DIjkstra implementation on 2D matrix, each time checking for 4 directions (Up, down, left, right)

What are the time and space complexities for this code? Why?

Problem link : https://www.geeksforgeeks.org/problems/minimum-cost-path3833/1

Problem title "Minimum Cost Path" from gfg

Code link : https://ideone.com/behL3F

int minimumCostPath(vector<vector<int>>& grid) 
    {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> cost(n,vector<int>(m,1e9));
        cost[0][0] = grid[0][0];
        
        priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, 
            greater<pair<int,pair<int,int>>>> pq;
        
        pq.push({cost[0][0],{0,0}});
        
        int row[] = {0,-1,0,1};
        int col[] = {1,0,-1,0};
        
        while(!pq.empty()){
            int cst = pq.top().first;
            int i = pq.top().second.first;
            int j = pq.top().second.second;
            pq.pop();
            
            for(int k=0;k<4;k++){
                int nr = i+row[k];
                int nc = j+col[k];
                
                if(nr<0 || nc<0 || nr>=n || nc>=m) continue;
                
                if(cost[nr][nc] > cst+grid[nr][nc]){
                    cost[nr][nc] = cst+grid[nr][nc];
                    pq.push({cost[nr][nc],{nr,nc}});
                }
            }
        }
        return cost[n-1][m-1];
    }
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Well Djikstra with priority queue is $$$O(m log n)$$$, so in your case it must be $$$O(mn log(mn))$$$

Because number of edges is $$$O(mn)$$$ (4 per cell and 3 for sides, 2 for corners) and number of nodes are $$$mn$$$