3 votes 3 votes While going through dijkstra's algorithm, there is a term "decrease key". I am not getting the meaning when it says "we do decrease key operation". What exactly we do and what is the meaning of decrease key ? Algorithms algorithms dijkstras-algorithm graph-theory + – Hitoshi asked Oct 15, 2017 • recategorized Jul 6, 2022 by Lakshman Bhaiya Hitoshi 1.7k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Rishabh Gupta 2 commented Oct 15, 2017 reply Follow Share We decrease key during relaxation. 0 votes 0 votes Hitoshi commented Oct 15, 2017 reply Follow Share @Rishab Gupta 2 thats what i am asking, what exactly we do during decrease key ? 0 votes 0 votes Rishabh Gupta 2 commented Oct 15, 2017 reply Follow Share we need to decrease the distance we calculated to a vertex if we have found a path to reach that vertex in a shorter distance. What I mean to say is, suppose currently the distance to reach a vertex v is d[v], from source node s, Later on, we found that we can reach v in a shorter distance. To check this we do relaxation, i.e. for a vertex, u, with distance from source vertex d[u], and v is connected to u with an edge of weight x, then if(d[v] > d[u] + x) This checks the condition if the previous distance to v is more than the distance of s to u and then u to v. If d[u] + x is less than d[v], then it says that we can reach v, from s, in a shorter distance than previously calculated in d[v]. so we change d[v] to d[u] + x, i.e. d[v] = d[u] + x, and change the parent pointers accordingly. This is relaxation. We generally use a min heap. And whenever we do the above step, we are decreasing the value of d[v]. This is decrease key. 4 votes 4 votes Please log in or register to add a comment.