MathCastle
Graph TheoryMediumGraph Algorithms

Graph Algorithms · Medium problem

A weighted graph has vertices s,a,b,c,ds,a,b,c,d and edges sa:6,sb:2,ab:3,ad:5,bc:4,cd:2sa{:}6, sb{:}2, ab{:}3, ad{:}5, bc{:}4, cd{:}2. A brand-new direct road sdsd is built with weight 77. By how much does the shortest-path distance from ss to dd decrease because of this new road?