MathCastle
Graph TheoryMediumGraph Algorithms

Graph Algorithms · Medium problem

A weighted graph has vertices s,a,b,c,d,ts,a,b,c,d,t and edges sa:4,sb:2,ac:3,bc:6,bd:5,ct:5,dt:7sa{:}4, sb{:}2, ac{:}3, bc{:}6, bd{:}5, ct{:}5, dt{:}7. A courier, without checking for a cheaper option, takes the route s→b→d→ts \to b \to d \to t. By how much more expensive is this than the TRUE shortest route from ss to tt?