### Gajanana's blog

By Gajanana, history, 3 months ago,

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 title "Minimum Cost Path" from gfg

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

• 0

 » 3 months ago, # |   0 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$