MathCastle
Graph TheoryChallengeGraph Algorithms

Graph Algorithms · Challenge problem

A weighted graph has vertices s,a,b,c,d,es,a,b,c,d,e and edges sa:2,sb:6,ab:3,ac:7,bd:5,cd:1,ce:8,de:3sa{:}2, sb{:}6, ab{:}3, ac{:}7, bd{:}5, cd{:}1, ce{:}8, de{:}3. Running Dijkstra's algorithm from ss, vertices are finalized one at a time in increasing order of their final distance (with ss itself finalized first). What is the distance of the 44th vertex to be finalized?