MathCastle
Graph TheoryChallengeGraph Algorithms

Graph Algorithms · Challenge problem

A weighted graph has vertices s,a,b,c,d,ts,a,b,c,d,t and edges sa:2,sb:2,ac:3,bc:3,ad:6,bd:6,ct:4,dt:1sa{:}2, sb{:}2, ac{:}3, bc{:}3, ad{:}6, bd{:}6, ct{:}4, dt{:}1. How many different routes from ss to tt achieve the shortest possible path length?