Shortest Path Algorithm

pic 1 In the Gate Level design of Soc timing check is our major tasks, it define some tags and constrains for timing libraries, such as "worst", "typical", and "beset" cases for each gates (Nodes)increment time, and "setup time" / "hold time" for each timing paths had exist, that constructed by one flip-flop through gates to another flip-flop. so in pic 1, we can figure out the output flip-flop had it's own fan-in paths, and all of them should meet the setup and hold timing constrain, if not, the flip-flops would get the wrong data in time strobe, in setup time fail means the data is slower than arrived, that we called longest path, hold time means the data is faster than arrived,that called shortest path and shortest path. so in here we use the Shortest Path to find out the shortest path in our case. how to adjust the violation paths to meet the constrain? in setup timing violation, we usually add latch design in our violation path,because it can hold data in each transaction,it means if the path is (2T) and our timing constrain is (1T),so the timing check would be failed,if we add the Latch design in it, that can separate our path in two parts, in here we assume first path is 1,5T, and second path is 0.4T , so total path time is (1.5+0.4) =1.9T. and the function module of latch is as same as flip-flop, so the timing path would be redefine in 2T, so the timing path 1.9T is match 2.T constrain. hold timing violation, add delay buffer.....